HDU 3549 Flow Problem (dinic模版 && isap模版)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3549

题意：

给你一个有向图，问你1到n的最大流。

dinic模版 (n*n*m)

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int N = ; //点个数

 const int M = ; //边个数

 const int inf = 0x3f3f3f3f;

 struct Edge {

     int to, next, cap, flow;

 }edge[M];

 int tot, head[N];

 void init() {

     tot = 0;

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

 }

 inline void add(int u, int v, int w, int rw = ) {

     edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = ;

     edge[tot].next = head[u]; head[u] = tot++;

     edge[tot].to = u; edge[tot].cap = rw; edge[tot].flow = ;

     edge[tot].next = head[v]; head[v] = tot++;

 }

 int Q[N];

 int dep[N], cur[N], sta[N];

 bool bfs(int s, int t, int n) {

     int front = , tail = ;

     memset(dep, -, sizeof(dep[])*(n + ));

     dep[s] = ;

     Q[tail++] = s;

     while(front < tail) {

         int u = Q[front++];

         for(int i = head[u]; ~i; i = edge[i].next) {

             int v = edge[i].to;

             if(edge[i].cap > edge[i].flow && dep[v] == -) {

                 dep[v] = dep[u] + ;

                 if(v == t)

                     return true;

                 Q[tail++] = v;

             }

         }

     }

     return false;

 }

 int dinic(int s, int t, int n) {

     int maxflow = ;

     while(bfs(s, t, n)) {

         for(int i = ; i < n; ++i)

             cur[i] = head[i];

         int u = s, tail = ;

         while(cur[s] != -) {

             if(u == t) {

                 int tp = inf;

                 for(int i = tail - ; i >= ; --i) {

                     tp = min(tp, edge[sta[i]].cap - edge[sta[i]].flow);

                 }

                 maxflow += tp;

                 for(int i = tail - ; i >= ; --i) {

                     edge[sta[i]].flow += tp;

                     edge[sta[i] ^ ].flow -= tp;

                     if(edge[sta[i]].cap - edge[sta[i]].flow == )

                         tail = i;

                 }

                 u = edge[sta[tail] ^ ].to;

             } else if(cur[u] != - && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] +  == dep[edge[cur[u]].to]) {

                 sta[tail++] = cur[u];

                 u = edge[cur[u]].to;

             } else {

                 while(u != s && cur[u] == -) {

                     u = edge[sta[--tail] ^ ].to;

                 }

                 cur[u] = edge[cur[u]].next;

             }

         }

     }

     return maxflow;

 }

 int main()

 {

     int t, n, m, u, v, c;

     scanf("%d", &t);

     for(int ca = ; ca <= t; ++ca) {

         scanf("%d %d", &n, &m);

         init();

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

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

             add(u, v, c);

         }

         printf("Case %d: %d\n", ca, dinic(, n, n));

     }

     return ;

 }

貌似一般比dinic更优一点

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int N = 1e3 + ;

 const int M = 1e4 + ;

 const int inf = 0x3f3f3f3f;

 struct Edge {

     int to, next, cap, flow;

 }edge[M];

 int tot, head[N], gap[N], dep[N], cur[N];

 void init() {

     tot = ;

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

 }

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

     edge[tot].next = head[u]; edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = ; head[u] = tot++;

     edge[tot].next = head[v]; edge[tot].to = u; edge[tot].cap = rw; edge[tot].flow = ; head[v] = tot++;

 }

 int Q[N];

 void bfs(int start, int end) {

     memset(dep, -, sizeof(dep));

     memset(gap, , sizeof(gap));

     gap[] = ;

     int front = , rear = ;

     dep[end] = ;

     Q[rear++] = end;

     while(front != rear) {

         int u = Q[front++];

         for(int i = head[u]; ~i; i = edge[i].next) {

             int v = edge[i].to;

             if(dep[v] != -)

                 continue;

             Q[rear++] = v;

             dep[v] = dep[u] + ;

             gap[dep[v]]++;

         }

     }

 }

 int S[N];

 int sap(int start, int end, int N) {

     bfs(start, end);

     memcpy(cur, head, sizeof(head));

     int top = ;

     int u = start;

     int ans = ;

     while(dep[start] < N) {

         if(u == end) {

             int Min = inf;

             int inser;

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

                 if(Min > edge[S[i]].cap - edge[S[i]].flow) {

                     Min = edge[S[i]].cap - edge[S[i]].flow;

                     inser = i;

                 }

             }

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

                 edge[S[i]].flow += Min;

                 edge[S[i] ^ ].flow -= Min;

             }

             ans += Min;

             top = inser;

             u = edge[S[top] ^ ].to;

             continue;

         }

         bool flag = false;

         int v;

         for(int i = cur[u]; ~i; i = edge[i].next) {

             v = edge[i].to;

             if(edge[i].cap - edge[i].flow && dep[v] +  == dep[u]) {

                 flag = true;

                 cur[u] = i;

                 break;

             }

         }

         if(flag) {

             S[top++] = cur[u];

             u = v;

             continue;

         }

         int Min = N;

         for(int i = head[u]; ~i; i = edge[i].next) {

             if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) {

                 Min = dep[edge[i].to];

                 cur[u] = i;

             }

         }

         gap[dep[u]]--;

         if(!gap[dep[u]])

             return ans;

         dep[u] = Min + ;

         gap[dep[u]]++;

         if(u != start)

             u = edge[S[--top] ^ ].to;

     }

     return ans;

 }

 int main()

 {

     int t, n, m, u, v, c;

     scanf("%d", &t);

     for(int ca = ; ca <= t; ++ca) {

         scanf("%d %d", &n, &m);

         init();

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

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

             addedge(u, v, c);

         }

         printf("Case %d: %d\n", ca, sap(, n, n));

     }

     return ;

 }