poj 1273 Drainage Ditches（网络流基础）

增广路算法。

Ford_Fullkerson

  1 /*
  2 Author:Zhaofa Fang
  3 Lang:C++
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <iostream>
  8 #include <cmath>
  9 #include <cstring>
 10 #include <algorithm>
 11 #include <string>
 12 #include <utility>
 13 #include <vector>
 14 #include <queue>
 15 #include <stack>
 16 #include <map>
 17 #include <set>
 18 using namespace std;
 19 
 20 typedef long long ll;
 21 const int INF = 2147483647;
 22 
 23 struct Edge
 24 {
 25     int v,c,next;
 26 }edge[1005];
 27 int eh[505],pp;
 28 int pre[505];
 29 int G[505][505];
 30 void init()
 31 {
 32     pp = 0;
 33     memset(eh,-1,sizeof(eh));
 34     memset(G,0,sizeof(G));
 35 }
 36 void add(int u,int v,int c)
 37 {
 38     edge[pp].v=v;
 39     edge[pp].c=c;
 40     edge[pp].next=eh[u];
 41     eh[u]=pp++;
 42 }
 43 void addedge(int u,int v,int c)
 44 {
 45     add(u,v,c);
 46     G[u][v]+=c;
 47     add(v,u,0);
 48     G[v][u]+=0;
 49 }
 50 int bfs(int s,int t)
 51 {
 52     queue<int> q;
 53     bool vist[505];
 54     memset(vist,0,sizeof(vist));
 55     q.push(s);
 56     vist[s]=1;
 57     while(!q.empty())
 58     {
 59         int now=q.front();q.pop();
 60         for(int i=eh[now];i!=-1;i=edge[i].next)
 61         {
 62             int v=edge[i].v;
 63             if(G[now][v] > 0 && !vist[v])
 64             {
 65                 vist[v]=1;
 66                 pre[v]=now;
 67                 if(v == t)return 1;
 68                 q.push(v);
 69             }
 70         }
 71     }
 72     return 0;
 73 }
 74 int Ford_Fullkerson(int s,int t,int &F)
 75 {
 76     memset(pre,0,sizeof(pre));
 77     int min=INF;
 78     if(bfs(s,t) == 0)return 0;
 79     for(int i=t;i!=s;i=pre[i])
 80     {
 81         if(G[pre[i]][i] < min)min=G[pre[i]][i];
 82     }
 83     for(int i=t;i!=s;i=pre[i])
 84     {
 85         G[pre[i]][i] -= min;
 86         G[i][pre[i]] += min;
 87     }
 88     F += min;
 89     return 1;
 90 }
 91 int main()
 92 {
 93     #ifndef ONLINE_JUDGE
 94     freopen("in","r",stdin);
 95     #endif
 96     int m,n;
 97     while(~scanf("%d%d",&m,&n))
 98     {
 99         int u,c,v;
100         init();
101         while(m--)
102         {
103             scanf("%d%d%d",&u,&v,&c);
104             addedge(u,v,c);
105         }
106         int F = 0;
107         while(Ford_Fullkerson(1,n,F));
108         cout<<F<<endl;
109     }
110     return 0;
111 }

sap_gap.

  1 /*
  2 Author:Zhaofa Fang
  3 Lang:C++
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <iostream>
  8 #include <cmath>
  9 #include <cstring>
 10 #include <algorithm>
 11 #include <string>
 12 #include <vector>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 using namespace std;
 18 
 19 typedef long long ll;
 20 const int INF = 2147483647;
 21 
 22 struct edge
 23 {
 24     int u,v;
 25     int cap,flow;
 26     int next;
 27 };
 28 int eh[505],tot;
 29 edge et[505<<1];
 30 void add(int u,int v,int cap,int flow)
 31 {
 32     edge E={u,v,cap,flow,eh[u]};
 33     et[tot]=E,eh[u]=tot++;
 34 }
 35 void addedge(int u,int v,int cap)
 36 {
 37     add(u,v,cap,0);add(v,u,0,0);
 38 }
 39 int cur[505],cnt[505],dist[505],pre[505];
 40 int low[505];
 41 int sap_gap(int s,int t,int n)
 42 {
 43     int u,v,now;
 44     memset(dist,0,sizeof(dist));
 45     memset(low,0,sizeof(low));
 46     for(u=0;u<=n;u++)cur[u] = eh[u];
 47     int flow=0;
 48     u = s;
 49     low[s] = INF;cnt[0] = n;
 50     while(dist[s] < n)
 51     {
 52         for(now = cur[u];now != -1;now = et[now].next)
 53             if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1)break;
 54         if(now != -1)
 55         {
 56             cur[u] = now;pre[v] = now;
 57             low[v] = et[now].cap - et[now].flow;
 58             low[v] = min(low[v],low[u]);
 59             u = v;
 60             if(u == t)
 61             {
 62                 for(;u != s;u = et[pre[u]].u)
 63                 {
 64                     et[pre[u]].flow += low[t];
 65                     et[pre[u]^1].flow -= low[t];
 66                 }
 67                 flow += low[t];low[s] = INF;
 68             }
 69         }
 70         else
 71         {
 72             if(--cnt[dist[u]] == 0)break;
 73             dist[u] = n;cur[u] = eh[u];
 74             for(now = eh[u];now != -1;now = et[now].next)
 75                 if(et[now].cap-et[now].flow > 0 && dist[u] > dist[et[now].v] + 1)
 76                     dist[u] = dist[et[now].v] + 1;
 77                 cnt[dist[u]]++;
 78                 if(u != s)u = et[pre[u]].u;
 79         }
 80     }
 81     return flow;
 82 }
 83 int n,m;
 84 void init()
 85 {
 86     tot = 0;
 87     memset(eh,-1,sizeof(eh));
 88 }
 89 
 90 int main()
 91 {
 92     #ifndef ONLINE_JUDGE
 93     freopen("in","r",stdin);
 94     #endif
 95     int a,b,c;
 96     while(~scanf("%d%d",&m,&n))
 97     {
 98         init();
 99         for(int i=1;i<=m;i++)
100         {
101             scanf("%d%d%d",&a,&b,&c);
102             addedge(a,b,c);
103 
104         }
105         printf("%d\n",sap_gap(1,n,n));
106     }
107     return 0;
108 }

sap

Dinic.O(V*V*E)

  1 Source Code
  2 
  3 Problem: 1273        User: qq6616323
  4 Memory: 716K        Time: 0MS
  5 Language: G++        Result: Accepted
  6 Source Code
  7 /*
  8  *Author:       Zhaofa Fang
  9  *Created time: 2013-07-13-10.25
 10  *Language:     C++
 11  */
 12 #include <cstdio>
 13 #include <cstdlib>
 14 #include <sstream>
 15 #include <iostream>
 16 #include <cmath>
 17 #include <cstring>
 18 #include <algorithm>
 19 #include <string>
 20 #include <utility>
 21 #include <vector>
 22 #include <queue>
 23 #include <map>
 24 #include <set>
 25 using namespace std;
 26 
 27 typedef long long ll;
 28 #define DEBUG(x) cout<< #x << ':' << x << endl
 29 #define FOR(i,s,t) for(int i = (s);i <= (t);i++)
 30 #define FORD(i,s,t) for(int i = (s);i >= (t);i--)
 31 #define REP(i,n) for(int i=0;i<(n);i++)
 32 #define REPD(i,n) for(int i=(n-1);i>=0;i--)
 33 #define PII pair<int,int>
 34 #define PB push_back
 35 #define MP make_pair
 36 #define ft first
 37 #define sd second
 38 #define lowbit(x) (x&(-x))
 39 #define INF (1<<30)
 40 #define eps 1e-8
 41 
 42 const int maxn = 505;
 43 const int maxm = 1010;
 44 struct Edge{
 45     int v,cap,flow,next;
 46 }edge[maxm];
 47 int eh[maxn],tot;
 48 int d[maxn];
 49 bool vist[maxn];
 50 
 51 void init(){
 52     tot = 0;
 53     memset(eh,-1,sizeof(eh));
 54 }
 55 void addedge(int u,int v,int c,int f){
 56     Edge e = {v,c,f,eh[u]};
 57     edge[tot] = e;
 58     eh[u] = tot ++;
 59 }
 60 void add(int u,int v,int c,int f){
 61     addedge(u,v,c,f);
 62     addedge(v,u,f,0);
 63 }
 64 
 65 bool BFS(int s,int t){
 66     memset(vist,0,sizeof(vist));
 67     queue<int>Q;
 68     Q.push(s);
 69     d[s] = 0;
 70     vist[s] = 1;
 71     while(!Q.empty()){
 72         int u = Q.front();
 73         Q.pop();
 74         for(int i=eh[u];i!=-1;i=edge[i].next){
 75             int v = edge[i].v;
 76             if(!vist[v] && edge[i].cap>edge[i].flow){
 77                  vist[v] = 1;
 78                  d[v] = d[u] + 1;
 79                  Q.push(v);
 80             }
 81         }
 82     }
 83     return vist[t];
 84 }
 85 int DFS(int u,int t,int avi){
 86     if(u == t || avi == 0)return avi;
 87     int flow = 0 , f;
 88     for(int i=eh[u];i!=-1;i=edge[i].next){
 89         int v = edge[i].v;
 90         if(d[u] + 1 == d[v] && (f=DFS(v,t,min(avi,edge[i].cap-edge[i].flow)))>0){
 91             edge[i].flow += f;
 92             edge[i^1].flow -= f;
 93             flow += f;
 94             avi -= f;
 95             if(avi == 0)break;
 96         }
 97     }
 98     return flow;
 99 }
100 int maxFlow(int s,int t){
101     int flow = 0;
102     while(BFS(s,t)){
103         flow += DFS(s,t,INF);
104     }
105     return flow;
106 }
107 int main(){
108     //freopen("in","r",stdin);
109     //freopen("out","w",stdout);
110     int n,m;
111     while(~scanf("%d%d",&n,&m)){
112         int u,v,c;
113         init();
114         while(n --){
115             scanf("%d%d%d",&u,&v,&c);
116             add(u,v,c,0);
117         }
118         printf("%d\n",maxFlow(1,m));
119     }
120     return 0;
121 }

Dinic

by Farmer