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

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

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

1 #include

2 #include

3 #include

4 #include

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 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]

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:\n",cse);

56 printf("%d\n\n",d[n]);

57 }

58 return 0;

59 }

 

精彩文章

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。