最大流基础

QC的博客搬来http://www.cnblogs.com/pony1993/archive/2012/07/28/2612883.html

模板题poj1273http://www.cnblogs.com/pony1993/archive/2012/07/28/2612883.html

代码

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define INF 0x3f3f3f
 7 using namespace std;
 8 int n,m,path[210],map[210][210],flow[210],st,en;
 9 int bfs()
10 {
11     int i,j,k;
12     memset(path,-1,sizeof(path));
13     path[st] = 0;
14     flow[st]= INF;
15     queue<int>q;
16     q.push(st);
17     while(!q.empty())
18     {
19         int mt = q.front();
20         q.pop();
21         if(mt==en)
22         break;
23         for(i = 1; i <= m ; i++)//找到新节点
24         {
25             if(i!=st&&path[i]==-1&&map[mt][i])
26             {
27                 flow[i] = min(flow[mt],map[mt][i]);//路径上的最小残量
28                 q.push(i);
29                 path[i] = mt;
30             }
31         }
32     }
33     if(path[en]==-1)
34     return -1;
35     return flow[en];
36 }
37 int karp()
38 {
39     int i,j,k,ml = 0,now,pre;
40     while((k=bfs())!=-1)//bfs找增广路径
41     {
42         ml+=k;
43         now = en;
44         while(now!=st)
45         {
46             pre = path[now];//path保留节点的前驱  更新正向边的实际容量
47             map[pre][now]-=k;
48             map[now][pre]+=k;//增加逆向边的容量
49             now = pre;
50         }
51     }
52     return ml;
53 }
54 int main()
55 {
56     int i,j,k,g,a,b,c;
57     while(cin>>n>>m)
58     {
59         memset(map,0,sizeof(map));
60         for(i = 1; i <= n ;i++)
61         {
62             cin>>a>>b>>c;
63             map[a][b]+=c;
64         }
65         st = 1,en = m;
66         cout<<karp()<<endl;
67     }
68     return 0;
69 }

多源点最大流

pojhttp://poj.org/problem?id=1459

增加一个源点与核电站相连一个终点与c相连 d看做平常的节点

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define INF 0x3f3f3f
 7 using namespace std;
 8 int path[110],map[110][110],flow[110],en,st,m;
 9 int bfs()
10 {
11     int i,j,k;
12     memset(path,-1,sizeof(path));
13     path[st] = 0;
14     flow[st] = INF;
15     queue<int>q;
16     q.push(st);
17     while(!q.empty())
18     {
19         int mt = q.front();
20         q.pop();
21         if(mt==en)
22         break;
23         for(i = 0; i <= en ; i++)
24         {
25             if(i!=st&&path[i]==-1&&map[mt][i])
26             {
27                 path[i] = mt;
28                 flow[i] = min(flow[mt],map[mt][i]);
29                 q.push(i);
30 
31             }
32         }
33     }
34     if(path[en]==-1)
35     return -1;
36     return flow[en];
37 }
38 int karp()
39 {
40     int i,j,k,now,ml=0,pre;
41     while((k=bfs())!=-1)
42     {
43         ml+=k;
44         now = en;
45         while(now!=st)
46         {
47             pre = path[now];
48             map[pre][now]-=k;
49             map[now][pre]+=k;
50             now = pre;
51         }
52     }
53     return ml;
54 }
55 int main()
56 {
57     int i,j,k,g,n,nc,np,u,v,w;
58     char str[20],c1,c2,c3;
59     while(cin>>n>>np>>nc>>m)
60     {
61         getchar();
62         memset(map,0,sizeof(map));
63         for(i = 1; i <= m ; i++)
64         {
65             cin>>c1>>u>>c2>>v>>c3>>w;
66             map[u][v] += w;
67         }
68         for(i = 1; i <= np ; i++)
69         {
70             cin>>c1>>u>>c2>>w;
71             map[n][u] += w;
72         }
73         for(i = 1; i <= nc ; i++)
74         {
75             cin>>c1>>u>>c2>>w;
76             map[u][n+1] += w;
77         }
78         st = n;
79         en = n+1;
80         cout<<karp()<<endl;
81     }
82     return 0;
83 }