Drainage Ditches（POJ1273+网络流+Dinic+EK）

题目链接：poj.org/problem?id=1273

题目：

题意：求最大流。

思路：测板子题，分别用Dinic和EK实现（我的板子跑得时间均为0ms）。

Dinic代码实现如下：

 #include <set>

 #include <map>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 typedef pair<ll, ll> pll;

 typedef pair<int, ll> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long ull;

 #define lson i<<1

 #define rson i<<1|1

 #define bug printf("*********\n");

 #define FIN freopen("D://code//in.txt", "r", stdin);

 #define debug(x) cout<<"["<<x<<"]" <<endl;

 #define IO ios::sync_with_stdio(false),cin.tie(0);

 const double eps = 1e-;

 const int mod = ;

 const int maxn =  + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const ll INF = 0x3f3f3f3f3f3f3f;

 int n, m, tot, maxflow, s, t, u, v, w;

 int head[maxn<<], d[maxn<<];

 queue<int> q;

 struct edge {

     int v, w, next;

 }ed[maxn<<];

 void addedge(int u, int v, int w) {

     ed[tot].v = v;

     ed[tot].w = w;

     ed[tot].next = head[u];

     head[u] = tot++;

     ed[tot].v = u;

     ed[tot].w = ;

     ed[tot].next = head[v];

     head[v] = tot++;

 }

 bool bfs() {

     memset(d, , sizeof(d));

     while(!q.empty()) q.pop();

     q.push(s);

     d[s] = ;

     while(!q.empty()) {

         int x = q.front(); q.pop();

         for(int i = head[x]; ~i; i = ed[i].next) {

             if(ed[i].w && !d[ed[i].v]) {

                 q.push(ed[i].v);

                 d[ed[i].v] = d[x] + ;

                 if(ed[i].v == t) return ;

             }

         }

     }

     return ;

 }

 int dinic(int x, int flow) {

     if(x == t) return flow;

     int rest = flow, k;

     for(int i = head[x]; ~i && rest; i = ed[i].next) {

         if(ed[i].w && d[ed[i].v] == d[x] + ) {

             k = dinic(ed[i].v, min(rest, ed[i].w));

             if(!k) d[ed[i].v] = ;

             ed[i].w -= k;

             ed[i^].w += k;

             rest -= k;

         }

     }

     return flow - rest;

 }

 int main() {

     //FIN;

     while(~scanf("%d%d", &m, &n)) {

         s = , t = n;

         tot = , maxflow = ;

         memset(head, -, sizeof(head));

         for(int i = ; i <= m; i++) {

             scanf("%d%d%d", &u, &v, &w);

             addedge(u, v, w);

         }

         int flow = ;

         while(bfs()) {

             while(flow = dinic(s, inf)) {

                 maxflow += flow;

             }

         }

         printf("%d\n", maxflow);

     }

     return ;

 }

EK实现如下：

 #include <set>

 #include <map>

 #include <queue>

 #include <stack>

 #include <cmath>

 #include <bitset>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 typedef pair<ll, ll> pll;

 typedef pair<int, ll> pil;;

 typedef pair<int, int> pii;

 typedef unsigned long long ull;

 #define lson i<<1

 #define rson i<<1|1

 #define bug printf("*********\n");

 #define FIN freopen("D://code//in.txt", "r", stdin);

 #define debug(x) cout<<"["<<x<<"]" <<endl;

 #define IO ios::sync_with_stdio(false),cin.tie(0);

 const double eps = 1e-;

 const int mod = ;

 const int maxn =  + ;

 const double pi = acos(-);

 const int inf = 0x3f3f3f3f;

 const ll INF = 0x3f3f3f3f3f3f3f;

 int n, m, u, v, w, tot, maxflow, s, t;

 int head[maxn<<], vis[maxn], incf[maxn], pre[maxn];

 struct edge {

     int v, w, next;

 }ed[maxn<<];

 void addedge(int u, int v, int w) {

     ed[tot].v = v;

     ed[tot].w = w;

     ed[tot].next = head[u];

     head[u] = tot++;

     ed[tot].v = u;

     ed[tot].w = ;

     ed[tot].next = head[v];

     head[v] = tot++;

 }

 bool bfs() {

     memset(vis, , sizeof(vis));

     queue<int> q;

     q.push(s);

     vis[s] = ;

     incf[s] = inf;

     while(!q.empty()) {

         int x = q.front();

         q.pop();

         for(int i = head[x]; i != -; i = ed[i].next) {

             if(ed[i].w) {

                 int v = ed[i].v;

                 if(vis[v]) continue;

                 incf[v] = min(incf[x], ed[i].w);

                 pre[v] = i;

                 q.push(v);

                 vis[v] = ;

                 if(v == t) return ;

             }

         }

     }

     return ;

 }

 void update() {

     int x = t;

     while(x != s) {

         int i = pre[x];

         ed[i].w -= incf[t];

         ed[i^].w += incf[t];

         x = ed[i^].v;

     }

     maxflow += incf[t];

 }

 int main() {

     //FIN;

     while(~scanf("%d%d", &m, &n)) {

         s = , t = n;

         tot = , maxflow = ;

         memset(head, -, sizeof(head));

         memset(pre, -, sizeof(pre));

         memset(incf, , sizeof(incf));

         for(int i = ; i <= m; i++) {

             scanf("%d%d%d", &u, &v, &w);

             addedge(u, v, w);

         }

         while(bfs()) update();

         printf("%d\n", maxflow);

     }

     return ;

 }