POJ1797 Heavy Transportation（SPFA）

题目要求1到n点的最大容量的增广路。

听说是最短路求的，然后乱搞就A了。。

大概能从Bellman-Ford的思想，d^k[u]表示从源点出发经过最多k条边到达u点的最短路，上理解正确性。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 #define INF (1<<30)
 7 #define MAXN 1111
 8 #define MAXM 1000111
 9 
10 struct Edge{
11     int v,cost,next;
12 }edge[MAXM];
13 int head[MAXN],NE;
14 void addEdge(int a,int b,int c){
15     edge[NE].v=b; edge[NE].cost=c; edge[NE].next=head[a];
16     head[a]=NE++;
17 }
18 
19 int d[MAXN];
20 int n,m;
21 void SPFA(){
22     bool vis[MAXN]={1,1};
23     for(int i=1; i<=n; ++i) d[i]=0;
24     d[1]=INF;
25     queue<int> que;
26     que.push(1);
27     while(!que.empty()){
28         int u=que.front(); que.pop();
29         for(int i=head[u]; i!=-1; i=edge[i].next){
30             int v=edge[i].v;
31             if(d[v]<min(d[u],edge[i].cost)){
32                 d[v]=min(d[u],edge[i].cost);
33                 if(!vis[v]){
34                     vis[v]=1;
35                     que.push(v);
36                 }
37             }
38         }
39         vis[u]=0;
40     }
41 }
42 int main(){
43     int t,a,b,c;
44     scanf("%d",&t);
45     for(int cse=1; cse<=t; ++cse){
46         scanf("%d%d",&n,&m);
47         NE=0;
48         memset(head,-1,sizeof(head));
49         while(m--){
50             scanf("%d%d%d",&a,&b,&c);
51             addEdge(a,b,c);
52             addEdge(b,a,c);
53         }
54         SPFA();
55         printf("Scenario #%d:
",cse);
56         printf("%d

",d[n]);
57     }
58     return 0;
59 }