さいだいりゅうきそ
19792 ワード
QCのブログはhttp://www.cnblogs.com/pony1993/archive/2012/07/28/2612883.html
テンプレート問題poj 1273 http://www.cnblogs.com/pony1993/archive/2012/07/28/2612883.html
コード#コード#
View Code
マルチソース最大ストリーム
poj http://poj.org/problem?id=1459
原子力発電所に接続するソースポイントを増やし、終点をcに接続するdを通常のノードと見なす
View Code
テンプレート問題poj 1273 http://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 }
マルチソース最大ストリーム
poj http://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 }