题目描述

如题，给出一个网络图，以及其源点和汇点，求出其网络最大流。

输入

第一行包含四个正整数N、M、S、T，分别表示点的个数、有向边的个数、源点序号、汇点序号。

接下来M行每行包含三个正整数ui、vi、wi，表示第i条有向边从ui出发，到达vi，边权为wi（即该边最大流量为wi）

输出

一行，包含一个正整数，即为该网络的最大流。

样例输入

4 5 4 34 2 304 3 202 3 202 1 301 3 40

样例输出

50

数据规模：

对于30%的数据：N<=10，M<=25

对于70%的数据：N<=200，M<=1000

对于100%的数据：N<=10000，M<=100000

网络流的模板题。汇总一些增广路算法。（Ford-Fulkerson, Edmond-Karp, Dinic, ISAP）

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 using namespace std;  7   8 struct edge {  9     int to,cap,rev; 10 }; 11  12 const int maxn=10001, INF=0x7F7F7F7F; 13 int n,m; 14 vector 
          
            G[maxn+1]; 15 16 edge make_edge(int to, int cap, int rev) { 17 edge x; 18 x.to=to, x.cap=cap, x.rev=rev; 19 return x; 20 } 21 22 void add_edge(int from, int to, int cap) { 23 G[from].push_back(make_edge(to,cap,G[to].size())); 24 G[to].push_back(make_edge(from,0,G[from].size()-1)); 25 } 26 27 void init() { 28 for (int i=1; i<=m; i++) { 29 int u,v,w; 30 scanf("%d%d%d",&u,&v,&w); 31 add_edge(u,v,w); 32 } 33 } 34 35 namespace Ford_Fulkerson { 36 bool used[maxn+1]; 37 38 int dfs(int x, int t, int f) { 39 if (x==t) return f; 40 used[x]=true; 41 for (int i=0; i
           
            0) { 44 int d=dfs(e.to,t,min(f,e.cap)); 45 if (d>0) { 46 e.cap-=d; 47 G[e.to][e.rev].cap+=d; 48 return d; 49 } 50 } 51 } 52 return 0; 53 } 54 55 int max_flow(int s, int t) { 56 int flow=0; 57 for(;;) { 58 memset(used,0,sizeof(used)); 59 int f=dfs(s,t,INF); 60 if (f==0) return flow; 61 flow+=f; 62 } 63 } 64 } 65 66 namespace Edmond_Karp { 67 bool vis[maxn+1]; 68 int prev[maxn+1]; 69 int pree[maxn+1]; 70 71 void bfs(int s) { 72 memset(vis,0,sizeof(vis)); 73 memset(prev,-1,sizeof(prev)); 74 memset(pree,-1,sizeof(pree)); 75 queue 
            
              q; 76 vis[s]=true; 77 q.push(s); 78 79 while(!q.empty()) { 80 int x=q.front(); 81 q.pop(); 82 for (int i=0; i
             
              0&&!vis[e.to]) { 85 prev[e.to]=x; 86 pree[e.to]=i; 87 vis[e.to]=true; 88 q.push(e.to); 89 } 90 } 91 } 92 } 93 94 int max_flow(int s, int t) { 95 int flow=0; 96 for(;;) { 97 bfs(s); 98 if (!vis[t]) return flow; 99 int d=INF;100 for (int i=t; prev[i]!=-1; i=prev[i])101 d=min(d,G[prev[i]][pree[i]].cap);102 for (int i=t; prev[i]!=-1; i=prev[i]) {103 edge &e=G[prev[i]][pree[i]];104 e.cap-=d;105 G[e.to][e.rev].cap+=d;106 }107 flow+=d;108 }109 }110 }111 112 namespace Dinic {113 int level[maxn+1];114 int iter[maxn+1];115 116 void bfs(int s) {117 memset(level,-1,sizeof(level));118 queue 
              
                q;119 level[s]=0;120 q.push(s);121 122 while (!q.empty()) {123 int x=q.front();124 q.pop();125 for (int i=0; i
               
                0&&level[e.to]<0) {128 level[e.to]=level[x]+1;129 q.push(e.to);130 }131 }132 }133 }134 135 int dfs(int x, int t, int f) {136 if (x==t) return f;137 for (int &i=iter[x]; i
                
                 0&&level[e.to]>level[x]) {140 int d=dfs(e.to,t,min(f,e.cap));141 if (d>0) {142 e.cap-=d;143 G[e.to][e.rev].cap+=d;144 return d;145 }146 }147 }148 return 0;149 }150 151 int max_flow(int s, int t) {152 int flow=0;153 for(;;) {154 bfs(s);155 if (level[t]<0) return flow;156 memset(iter,0,sizeof(iter));157 int f;158 while ((f=dfs(s,t,INF))>0)159 flow+=f;160 }161 }162 }163 164 namespace ISAP {165 int gap[maxn+1];166 int iter[maxn+1];167 int level[maxn+1];168 169 void bfs(int t) {170 memset(gap,0,sizeof(gap));171 memset(level,-1,sizeof(level));172 queue 
                 
                   q;173 level[t]=1;174 gap[level[t]]=1;175 q.push(t);176 177 while (!q.empty()) {178 int x=q.front();179 q.pop();180 for (int i=0; i
                  
                   0&&level[x]==level[e.to]+1) {197 int d=dfs(e.to,s,t,min(f-flow,e.cap));198 e.cap-=d;199 G[e.to][e.rev].cap+=d;200 flow+=d;201 if (f==flow) return f;202 }203 }204 205 gap[level[x]]--;206 if (gap[level[x]]==0)207 level[s]=n+1;208 iter[x]=0;209 gap[++level[x]]++;210 return flow;211 }212 213 int max_flow(int s, int t) {214 int flow=0;215 bfs(t);216 memset(iter,0,sizeof(iter));217 while (level[s]<=n)218 flow+=dfs(s,s,t,INF);219 return flow;220 }221 }222 223 int main() {224 int s,t;225 scanf("%d%d%d%d",&n,&m,&s,&t);226 init();227 printf("%d\n",ISAP::max_flow(s,t));228 return 0;229 }