首页 > ACM题库 > HDU-杭电 > hdu 2485 Destroying the bus stations-最短路径-[解题报告]C++
2014
01-26

hdu 2485 Destroying the bus stations-最短路径-[解题报告]C++

Destroying the bus stations

问题描述 :

Gabiluso is one of the greatest spies in his country. Now he’s trying to complete an “impossible” mission —– to make it slow for the army of City Colugu to reach the airport. City Colugu has n bus stations and m roads. Each road connects two bus stations directly, and all roads are one way streets. In order to keep the air clean, the government bans all military vehicles. So the army must take buses to go to the airport. There may be more than one road between two bus stations. If a bus station is destroyed, all roads connecting that station will become no use. What’s Gabiluso needs to do is destroying some bus stations to make the army can’t get to the airport in k minutes. It takes exactly one minute for a bus to pass any road. All bus stations are numbered from 1 to n. The No.1 bus station is in the barrack and the No. n station is in the airport. The army always set out from the No. 1 station.
No.1 station and No. n station can’t be destroyed because of the heavy guard. Of course there is no road from No.1 station to No. n station.

Please help Gabiluso to calculate the minimum number of bus stations he must destroy to complete his mission.

输入:

There are several test cases. Input ends with three zeros.

For each test case:

The first line contains 3 integers, n, m and k. (0< n <=50, 0< m<=4000, 0 < k < 1000)
Then m lines follows. Each line contains 2 integers, s and f, indicating that there is a road from station No. s to station No. f.

输出:

There are several test cases. Input ends with three zeros.

For each test case:

The first line contains 3 integers, n, m and k. (0< n <=50, 0< m<=4000, 0 < k < 1000)
Then m lines follows. Each line contains 2 integers, s and f, indicating that there is a road from station No. s to station No. f.

样例输入:

5 7 3
1 3
3 4
4 5
1 2
2 5
1 4
4 5
0 0 0

样例输出:

2


题目意思是说,摧毁车站,那么与车站相连的路就都失效了,因此想到了将一个点分拆为两个点,例如节点2,那么就分拆为节点2和3,并在2和3之加一条边,容量为1,费用为0,如果原来1到2有路,那么现在就变成了1到分拆出来的2有路,如果原来2到x有路,那么现在就变成了分拆出来的3到x有路,这样的话用最小费用算法在图上进行曾流的时候,没曾一次流就相当于在摧毁车站,因为车站被拆分成了两个点,并且容量为1

#include<iostream>
#include<queue>
using namespace std;
struct Node{
int here,adj;
int flow,cost;
int next;
};
int head[10000];
Node edges[1000000];
int loc;
int s,t;
void addEdge(int here,int adj,int flow,int cost){
edges[loc].here=here,edges[loc].adj=adj,edges[loc].flow=flow,edges[loc].cost=cost;
edges[loc].next=head[here],head[here]=loc++;
edges[loc].here=adj,edges[loc].adj=here,edges[loc].flow=0,edges[loc].cost=-cost;
edges[loc].next=head[adj],head[adj]=loc++;
}
int n,r,k;
bool visit[100];
int dis[100];
int father[100];
bool spfa(){
memset(dis,-1,sizeof(dis));
memset(father,-1,sizeof(father));
memset(visit,false,sizeof(visit));
int now=s;
dis[now]=0;
visit[now]=true;
queue<int> qu;
qu.push(now);
while(!qu.empty()){
now=qu.front(),qu.pop();
visit[now]=false;
int p;
for(p=head[now];p!=-1;p=edges[p].next){
if(edges[p].flow>0){
int temp=dis[now]+edges[p].cost;
if(dis[edges[p].adj]==-1||temp<dis[edges[p].adj]){
dis[edges[p].adj]=temp;
father[edges[p].adj]=p;
if(!visit[edges[p].adj]){
visit[edges[p].adj]=true;
qu.push(edges[p].adj);
}
}
}
}
}
return dis[t]>0&&dis[t]<=k;
}
int mincost(){
int flow=0;
while(spfa()){
int end=father[t];
int min=1000000;
while(end!=-1){
min=edges[end].flow<min?edges[end].flow:min;
end=father[edges[end].here];
}
flow+=min;
end=father[t];
while(end!=-1){
edges[end].flow-=min;
edges[end^1].flow+=min;
end=father[edges[end].here];
}
}
return flow;
}
int main(){
while(scanf(“%d%d%d”,&n,&r,&k),n){
s=1,t=2*n-2;
memset(head,-1,sizeof(head));
loc=0;
for(int i=1;i<n-1;i++){
            addEdge(2*i,2*i+1,1,0);
        }
for( i=1;i<=r;i++){
int a,b;
scanf(“%d%d”,&a,&b);
a–,b–;
addEdge(2*a+1,2*b,1,1);
}
printf(“%d\n”,mincost());
}
return 0;
}

解题转自:http://2225377fjs.blog.163.com/blog/static/1746298372011116112013244/


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?