Ford_Fulkerson (O(F*E))
感觉不会用到,但还是写一下吧...
复杂度 : 最大流量为 F ,每次最少增广 1 ,最多增广 F 次,每一次最多跑 E 条边(整张图).
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 #define rep(i,n) for(int i=0;i<(n);i++) 6 #define for1(i,a,n) for(int i=(a);i<=(n);i++) 7 #define CC(i,a) memset(i,a,sizeof(i)) 8 #define read(a) a=getnum() 9 #define print(a) printf("%d",a) 10 using namespace std; 11 12 const int maxn=205,INF=0x7fffffff; 13 struct edge { int to,cap,rev; }; 14 int m,n; 15 bool vis[maxn]; 16 vector <edge> g[maxn]; 17 18 inline int getnum(){ int r=0,k=1;char c;for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') k=-1;for(;c>='0'&&c<='9';c=getchar()) r=r*10+c-'0'; return r*k; } 19 20 void add_edge(int from,int to,int cap) 21 { 22 g[from].push_back((edge) { to,cap,g[to].size() }); 23 g[to].push_back((edge) { from,0,g[from].size()-1 }); 24 } 25 26 int dfs(int v,int t,int f) 27 { 28 if(v==t) return f; 29 vis[v]=true; 30 rep(i,g[v].size()) 31 { 32 edge &e=g[v][i]; 33 if(!vis[e.to]&&e.cap>0) 34 { 35 int d=dfs(e.to,t,min(f,e.cap)); 36 if(d>0) 37 { 38 e.cap-=d; 39 g[e.to][e.rev].cap+=d; 40 return d; 41 } 42 } 43 } 44 return 0; 45 } 46 47 int max_flow(int s,int t) 48 { 49 CC(vis,false); 50 int flow=0,f; 51 while((f=dfs(s,t,INF))>0) 52 { 53 flow+=f; 54 CC(vis,false); 55 } 56 return flow; 57 } 58 59 void init() 60 { 61 read(m); read(n); 62 for1(i,1,m) 63 { 64 int from,to,cap; 65 read(from); read(to); read(cap); 66 add_edge(from,to,cap); 67 } 68 } 69 70 int main() 71 { 72 init(); 73 print(max_flow(1,n)); 74 return 0; 75 }
Dinic (O(E*V^2))
复杂度 : 每一张层级图跑完,说明最短增广路要变长了, 重新 bfs 构造新的层级图时最短增广路至少要 +1 ,长度最多为 V - 1 ,所以最多有 ( V - 1 ) 个层级图.在每一个层级图中,每一条增广路都有至少一个瓶颈(路上 cap 最小的弧),跑完这条最短路后这个弧就没有了(因为走了正向所以反向弧不符合 level ,不会在这一张层级图中走了),最多 E 条弧,每次至少消去一条,那最多跑 E 次,每一次最多跑 V 个点,所以在一张层级图里最多跑 E * V 次,综上,总复杂度是O(E*V^2).
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<queue> 5 #include<algorithm> 6 #define rep(i,n) for(int i=0;i<n;i++) 7 #define for1(i,a,n) for(int i=(a);i<=(n);i++) 8 #define CC(i,a) memset(i,a,sizeof(i)) 9 #define read(a) a=getnum() 10 #define print(a) printf("%d ",a) 11 using namespace std; 12 13 const int maxn=205,INF=0x7fffffff; 14 int m,n; 15 int iter[maxn],level[maxn]; 16 struct edge { int to,cap,rev; }; 17 vector <edge> g[maxn]; 18 19 inline int getnum() { int r=0,k=1;char c;for(c=getchar();c<'0'||c>'9';c=getchar()) if(c==-'-') k=-1;for(;c>='0'&&c<='9';c=getchar()) r=r*10+c-'0'; return r*k; } 20 21 void add_edge(int from,int to,int cap) 22 { 23 g[from].push_back((edge) { to,cap,g[to].size() }); 24 g[to].push_back((edge) { from,0,g[from].size()-1 }); 25 } 26 27 void bfs(int s) 28 { 29 CC(level,-1); 30 level[s]=1; 31 queue <int> q; 32 q.push(s); 33 while(!q.empty()) 34 { 35 int t=q.front(); q.pop(); 36 rep(i,g[t].size()) 37 { 38 edge &e=g[t][i]; 39 if(level[e.to]<0&&e.cap>0) 40 { 41 level[e.to]=level[t]+1; 42 q.push(e.to); 43 } 44 } 45 } 46 } 47 48 int dfs(int v,int t,int f) 49 { 50 if(v==t) return f; 51 for(int &i=iter[v];i<g[v].size();i++) 52 { 53 edge &e=g[v][i]; 54 if(e.cap>0&&level[v]<level[e.to]) 55 { 56 int d=dfs(e.to,t,min(f,e.cap)); 57 if(d>0) 58 { 59 e.cap-=d; 60 g[e.to][e.rev].cap+=d; 61 return d; 62 } 63 } 64 } 65 return 0; 66 } 67 68 int max_flow(int s,int t) 69 { 70 int flow=0; 71 bfs(s); 72 while(level[t]>0) 73 { 74 CC(iter,0); 75 int f; 76 while((f=dfs(s,t,INF))>0) flow+=f; 77 bfs(s); 78 } 79 return flow; 80 } 81 82 void init() 83 { 84 read(m); read(n); 85 for1(i,1,m) 86 { 87 int from,to,cap; 88 read(from); read(to); read(cap); 89 add_edge(from,to,cap); 90 } 91 } 92 93 int main() 94 { 95 init(); 96 print(max_flow(1,n)); 97 return 0; 98 } 99 100 101 102 103 104