1 #include<iostream> 2 /* 3 題意：就是尋找從源點到匯點的最大流！ 4 要注意的是每兩個點的流量可能有多個，也就是說有重邊，所以要把兩個點的所有的流量都加起來 5 就是這兩個點之間的流量了！ 6 7 思路：建圖之后直接套用最大流算法（EK, 或者是Dinic算法） 圖解Dinic算法流程！
8 */ 9 #include<queue> 10 #include<cstring> 11 #include<cstdio> 12 #include<algorithm> 13 #define INF 0x3f3f3f3f3f3f3f3f 14 #define N 205 15 using namespace std; 16 typedef long long LL; 17 LL cap[N][N]; 18 19 int m, n; 20 LL maxFlow; 21 int d[N]; 22 queue<int>q; 23 24 bool bfs(){ 25 q.push(1); 26 memset(d, 0, sizeof(d)); 27 d[1]=1; 28 while(!q.empty()){ 29 int u=q.front(); 30 q.pop(); 31 for(int v=1; v<=n; ++v) 32 if(!d[v] && cap[u][v]>0){ 33 d[v]=d[u]+1; 34 q.push(v); 35 } 36 } 37 if(!d[n]) return false; 38 return true; 39 } 40 41 LL dfs(int u, LL flow){ 42 if(u==n) return flow; 43 for(int v=1; v<=n; ++v) 44 if(d[v]==d[u]+1 && cap[u][v]>0){ 45 LL a=dfs(v, min(flow, cap[u][v])); 46 if(a==0) continue;//如果a==0 說明沒有找到從起點到匯點的增廣路， 然后換其他路接著尋找！ 47 cap[u][v]-=a; 48 cap[v][u]+=a; 49 return a; 50 } 51 return 0; 52 } 53 54 void Dinic(){ 55 LL flow; 56 while(bfs()){//利用bfs構造好層次圖，這樣dfs在尋找阻塞流的時候，就不會盲目的尋找了！ 57 while(flow=dfs(1, INF)) maxFlow+=flow;//利用構造好的層次圖不斷的尋找阻塞流！ 58 } 59 } 60 61 int main(){ 62 while(scanf("%d%d", &m, &n)!=EOF){ 63 memset(cap, 0, sizeof(cap)); 64 while(m--){ 65 int u, v; 66 LL w; 67 scanf("%d%d%lld", &u, &v, &w); 68 cap[u][v]+=w; 69 } 70 maxFlow=0; 71 Dinic(); 72 printf("%lld\n", maxFlow); 73 } 74 return 0; 75 }
1 //EK算法同樣搞定 2 #include<iostream> 3 #include<queue> 4 #include<cstdio> 5 #include<cstring> 6 #include<algorithm> 7 #define INF 0x3f3f3f3f 8 using namespace std; 9 typedef __int64 LL; 10 LL cap[205][205]; 11 int pre[205]; 12 LL a[205]; 13 int m, n; 14 queue<int>q; 15 LL maxFlow; 16 bool spfa(){ 17 while(!q.empty()) q.pop(); 18 memset(a, 0, sizeof(a)); 19 q.push(1); 20 a[1]=INF; 21 while(!q.empty()){ 22 int u=q.front(); 23 q.pop(); 24 for(int v=1; v<=n; ++v) 25 if(!a[v] && cap[u][v]>0){ 26 pre[v]=u; 27 a[v]=min(a[u], cap[u][v]); 28 q.push(v); 29 } 30 if(a[n]) break; 31 } 32 if(!a[n]) return false; 33 return true; 34 } 35 36 void EK(){ 37 maxFlow=0; 38 while(spfa()){ 39 int u=n; 40 maxFlow+=a[n]; 41 while(u!=1){ 42 cap[pre[u]][u]-=a[n]; 43 cap[u][pre[u]]+=a[n]; 44 u=pre[u]; 45 } 46 } 47 } 48 int main(){ 49 while(scanf("%d%d", &m, &n)!=EOF){ 50 memset(cap, 0, sizeof(cap)); 51 while(m--){ 52 int u, v; 53 LL w; 54 scanf("%d%d%I64d", &u, &v, &w); 55 cap[u][v]+=w; 56 } 57 EK(); 58 printf("%I64d\n", maxFlow); 59 } 60 return 0; 61 }
?
?
)
