POJ 1273 Drainage Ditches(最大ストリームテンプレートEK+dinic)
17849 ワード
タイトルリンク
この2つのテンプレートに詳しい.この2つの考え方はあまり悪くなくて、実现の方式はある程度异なって、dinicは少し速いべきで、しかしPOJの上ですべて16 msです....
dinicアルゴリズム
EKアルゴリズム
この2つのテンプレートに詳しい.この2つの考え方はあまり悪くなくて、実现の方式はある程度异なって、dinicは少し速いべきで、しかしPOJの上ですべて16 msです....
dinicアルゴリズム
1 #include <cstdio>//dinic
2 #include <cstring>
3 #include <cmath>
4 #include <queue>
5 using namespace std;
6 #define INF 0x7fffffff
7 queue<int> que;
8 int flow[201][201],dis[201];
9 int n,m;
10 int bfs()
11 {
12 int t,i;
13 memset(dis,-1,sizeof(dis));
14 while(!que.empty()) que.pop();
15 que.push(1);
16 dis[1] = 0;
17 while(!que.empty())
18 {
19 t = que.front();
20 que.pop();
21 for(i = 1;i <= n;i ++)
22 {
23 if(flow[t][i] > 0&&dis[i] < 0)
24 {
25 dis[i] = dis[t]+1;
26 que.push(i);
27 }
28 }
29 }
30 if(dis[n] > 0) return 1;
31 else return 0;
32 }
33 int dfs(int x,int step)
34 {
35 int i,t;
36 if(x == n) return step;
37 for(i = 1;i <= n;i ++)
38 {
39 if(flow[x][i] > 0&&dis[i] == dis[x]+1&&(t = dfs(i,min(step,flow[x][i]))))
40 {
41 flow[x][i] -= t;
42 flow[i][x] += t;
43 return t;
44 }
45 }
46 return 0;
47 }
48 int main()
49 {
50 int i,sv,ev,w,res,ans;
51 while(scanf("%d%d",&m,&n)!=EOF)
52 {
53 ans = 0;
54 memset(flow,0,sizeof(flow));
55 for(i = 1;i <= m;i ++)
56 {
57 scanf("%d%d%d",&sv,&ev,&w);
58 flow[sv][ev] += w;
59 }
60 while(bfs())
61 {
62 while(res = dfs(1,INF))
63 ans += res;
64 }
65 printf("%d
",ans);
66 }
67 return 0;
68 }
EKアルゴリズム
1 #include <cstdio>
2 #include <cstring>
3 #include <cmath>
4 #include <queue>
5 using namespace std;
6 #define INF 0x7fffffff
7 queue<int> que;
8 int flow[201][201],low[201],path[201];
9 int str,end,n,m;
10 int bfs()
11 {
12 int t,i;
13 memset(path,-1,sizeof(path));
14 while(!que.empty()) que.pop();
15 que.push(str);
16 low[str] = INF;
17 while(!que.empty())
18 {
19 t = que.front();
20 que.pop();
21 if(t == end) break;
22 for(i = 1;i <= n;i ++)
23 {
24 if(i != str&&path[i]==-1&&flow[t][i])
25 {
26 low[i] = low[t] < flow[t][i] ? low[t]:flow[t][i];
27 path[i] = t;
28 que.push(i);
29 }
30 }
31 }
32 if(path[end] == -1)
33 return -1;
34 else
35 return low[end];
36 }
37 int EK()
38 {
39 int ans = 0,res,now;
40 while((res = bfs()) != -1)
41 {
42 ans += res;
43 now = end;
44 while(now != str)
45 {
46 flow[now][path[now]] += res;
47 flow[path[now]][now] -= res;
48 now = path[now];
49 }
50 }
51 return ans;
52 }
53 int main()
54 {
55 int i,sv,ev,w;
56 while(scanf("%d%d",&m,&n)!=EOF)
57 {
58 memset(flow,0,sizeof(flow));
59 for(i = 1;i <= m;i ++)
60 {
61 scanf("%d%d%d",&sv,&ev,&w);
62 flow[sv][ev] += w;
63 }
64 str = 1,end = n;
65 printf("%d
",EK());
66 }
67 return 0;
68 }