hdoj 3549最大流模板

应用karp算法找最大流的模板题，对最大流一直都是不很懂，看着别人的代码打完这个感觉像是懂了点，就是一直找增广路径，直到找不到为止，求出来的就是整个的最大流

View Code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #define min(x,y) x<y?x:y
 6 #define N 20
 7 #define inf 0x7fffffff
 8 using namespace std;
 9 int tcase,n,m;
10 int map[N][N],flow[N],path[N];
11 int make_point(int s,int e)
12 {
13     queue<int> q;
14     while(!q.empty())
15     q.pop();
16     int t,i;
17     memset(path,0,sizeof(path));
18     flow[s]=inf;
19     path[s]=inf;
20     q.push(s);
21     while(!q.empty())
22     {
23         t=q.front();
24         q.pop();
25         if(t==e)
26         break;
27         for(i=1;i<=n;i++)
28         {
29             if(map[t][i]&&!path[i]&&i!=s)
30             {
31                 path[i]=t;
32                 flow[i]=min(flow[t],map[t][i]);
33                 q.push(i);
34             }
35         }
36     }
37     if(path[e]==0)
38     return -1;
39     return flow[e];
40 }
41 int karp(int s,int e)
42 {
43     int i,j;
44     int incr,step,curr,prev;
45     incr=0;
46     while((step=make_point(s,e))!=-1)
47     {
48         incr+=step;
49         curr=e;
50         while(curr!=s)
51         {
52             prev=path[curr];
53             map[prev][curr]-=step;
54             map[curr][prev]+=step;
55             curr=prev;
56         }
57     }
58     return incr;
59 }
60 int main()
61 {
62     int i,j,k,x,y,c;
63     int icase;
64     while(scanf("%d",&tcase)!=EOF)
65     {
66         icase=1;
67         while(tcase--)
68         {
69             scanf("%d%d",&n,&m);
70             memset(map,0,sizeof(map));
71             while(m--)
72             {
73                 scanf("%d%d%d",&x,&y,&c);
74                 map[x][y]+=c;
75             }
76             printf("Case %d: %d\n",icase++,karp(1,n));
77         }
78     }
79     return 0;
80 }