题目太恶心了。
描述那么多都是鸡肋 = =。。
多源点多汇点。给出道路连接的最大容量，给出源点容量和汇点容量，求最大流而已 = =。。。这题目太恶心了，太恶心了。看了半天才看懂。
本来想用dinic的，找的非递归的模板有问题 = =。。。
递归的dinic都比EK快一倍。。理解着真的好难啊。。。
刚试着用邻接表写，很顺利地写下来了，嘻嘻~~
EK zoj 400+MS
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 120 using namespace std; int n,np,nc,m; int cap[MAX][MAX]; int EKarp(int s,int t) { queue<int> Q; int flow[MAX][MAX],a[MAX],u,v,f,pre[MAX]; f = 0; memset(flow,0,sizeof(flow)); while(1) { Q.push(s); memset(a,0,sizeof(a)); a[s] = INT_MAX; while( !Q.empty() ) { u = Q.front(); Q.pop(); for(v=0; v<=t; v++) if( !a[v] && cap[u][v] > flow[u][v] ) { Q.push(v); a[v] = a[u] < cap[u][v] - flow[u][v] ? a[u] : cap[u][v] - flow[u][v]; pre[v] = u; } } if( a[t] == 0 ) break; for(u=t; u!=s; u=pre[u]) { flow[pre[u]][u] += a[t]; flow[u][pre[u]] -= a[t]; } f += a[t]; } return f; } int main() { char ch; int from,to,len,ans; while( ~scanf("%d%d%d%d",&n,&np,&nc,&m) ) { memset(cap,0,sizeof(cap)); while( m-- ) { scanf(" (%d,%d)%d",&from,&to,&len); cap[from][to] = len; } while( np-- ) { scanf(" (%d)%d",&from,&len); cap[n+1][from] = len; } while( nc-- ) { scanf(" (%d)%d",&from,&len); cap[from][n+2] = len; } ans = EKarp(n+1,n+2); printf("%d/n",ans); } return 0; }
递归的Dinic zoj 200+ms
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 120 using namespace std; int n,np,nc,m; int cap[MAX][MAX],s,t; int pre[MAX],lev[MAX]; queue<int> q; int BFS(int s) { int u,v; memset(lev,-1,sizeof(lev)); q.push(s); lev[s] = 0; while( !q.empty() ) { u = q.front(); q.pop(); for(v=0; v<=t; v++) if( cap[u][v] > 0 && lev[v] == -1 ) { lev[v] = lev[u] + 1; q.push(v); } } return lev[t] != -1; } int Dinic(int k,int sum) { int i,a,os; if ( k == t) return sum; os = sum; for(i=0; i<=t && sum; i++) if( lev[i]==lev[k]+1 && cap[k][i] > 0 ) { a = Dinic( i, min(sum,cap[k][i]) ); cap[k][i]-=a; cap[i][k]+=a; sum -= a; } return os-sum; } int main() { char ch; int from,to,len,ans; while( ~scanf("%d%d%d%d",&n,&np,&nc,&m) ) { memset(cap,0,sizeof(cap)); while( m-- ) { scanf(" (%d,%d)%d",&from,&to,&len); cap[from][to] = len; } while( np-- ) { scanf(" (%d)%d",&from,&len); cap[n+1][from] = len; } while( nc-- ) { scanf(" (%d)%d",&from,&len); cap[from][n+2] = len; } s = n+1; t = n+2; ans = 0; while( BFS(s) ) ans += Dinic(s,INT_MAX); printf("%d/n",ans); } return 0; }
非递归的 dinic zoj 40MS 哇咔咔
/* * 2400551 2011-02-10 10:32:59 Accepted 1734 C++ 40 228 小媛在努力 * 看懂dinic了 ^ ^ * 哇咔咔~~/(^o^)/~ * zoj排第二，节省不了内存了 T T。。 * 其实。。刷排名的做法蛮猥琐的。。 */ #include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 103 using namespace std; int n,np,nc,m; int cap[MAX][MAX]; int lev[MAX]; queue<int> q; int BFS(int s,int t) { int u,v; memset(lev,-1,sizeof(lev)); q.push(s); lev[s] = 0; while( !q.empty() ) { u = q.front(); q.pop(); for(v=0; v<=t; v++) if( cap[u][v] > 0 && lev[v] == -1 ) { lev[v] = lev[u] + 1; q.push(v); } } return lev[t] != -1; } int Dinic(int s,int t) { int a[MAX],cur[MAX]; int pre[MAX]; int flow = 0; int i,u,flag,v,ag,k; while( BFS(s,t) ) { for(i=0; i<=t; i++) { // cur里初始化是第一个节点哈 cur[i] = 0; // DFS中，如果需要回溯，就回溯到cur中的节点。 a[i] = INT_MAX; // a里面存的是剩余流量 } u = s; while(1) { flag = 0; for(v=cur[u]; v<=t; v++) if( cap[u][v] > 0 && lev[u] + 1 == lev[v] ) { flag = 1; break; } if( flag ) { cur[u] = v + 1; pre[v] = u; a[v] = cap[u][v]; if( a[v] > a[u] ) a[v] = a[u]; u = v; // 从找到的节点后开始在层次图里找路 if( u == t ) // 找到t后，增广 { ag = a[t]; flow += ag; for(v=t; v!=s; v=pre[v]) { cur[pre[v]] = v; // 退回上一步。。 cap[pre[v]][v] -= ag; cap[v][pre[v]] += ag; a[v] -= ag; if( cap[pre[v]][v] == 0 ) u = pre[v]; } } } else if( u != s ) // 如果u ！= s 那么这条路走不通的话，从u的上一个节点继续找。 { lev[u] = INT_MAX; // 相当于从层次图里删除这个节点。 u = pre[u]; } else // 如果从源点找不到增广路，就结束咧。 break; } } return flow; } int main() { char ch; int from,to,len,ans; while( ~scanf("%d%d%d%d",&n,&np,&nc,&m) ) { memset(cap,0,sizeof(cap)); while( m-- ) { scanf(" (%d,%d)%d",&from,&to,&len); cap[from][to] = len; } while( np-- ) { scanf(" (%d)%d",&from,&len); cap[n+1][from] = len; } while( nc-- ) { scanf(" (%d)%d",&from,&len); cap[from][n+2] = len; } ans = Dinic(n+1,n+2);; printf("%d/n",ans); } return 0; }
非递归dinic + 邻接表 zoj 60ms
/* * 2400843 2011-02-10 19:24:44 Accepted 1734 C++ 60 520 小媛在努力 * dinic + 邻接表，理解用数组代替指针后，这个写着顺当多了。。。 */ #include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 103 using namespace std; int n,np,nc,m; int lev[MAX]; typedef struct NODE{ int from,to,cap; int next; }NODE; NODE node[MAX*MAX*2]; int cou,net[MAX]; void init() { cou = 2; memset(node,'/0',sizeof(node)); memset(net,-1,sizeof(net)); } queue<int> q; int BFS(int s,int t) { int u,v,head,cap; memset(lev,-1,sizeof(lev)); q.push(s); lev[s] = 0; while( !q.empty() ) { u = q.front(); q.pop(); head = net[u]; while( head != -1 ) { v = node[head].to; cap = node[head].cap; if( cap > 0 && lev[v] == -1 ) { lev[v] = lev[u] + 1; q.push(v); } head = node[head].next; } } return lev[t] != -1; } int Dinic(int s,int t) { int a[MAX],cur[MAX]; int pos[MAX],pre[MAX]; int flow = 0,head,cap; int i,u,flag,v,ag,k; while( BFS(s,t) ) { for(i=0; i<=t; i++) a[i] = INT_MAX; // a里面存的是剩余流量 u = s; while(1) { flag = 0; head = net[u]; while( head != -1 ) { cap = node[head].cap; v = node[head].to; if( cap > 0 && lev[u] + 1 == lev[v] ) { pos[v] = head; flag = 1; break; } head = node[head].next; } if( flag ) { pre[v] = u; a[v] = cap; if( a[v] > a[u] ) a[v] = a[u]; u = v; // 从找到的节点后开始在层次图里找路 if( u == t ) // 找到t后，增广 { ag = a[t]; flow += ag; for(v=t; v!=s; v=pre[v]) { node[pos[v]^1].cap += ag; node[pos[v]].cap -= ag; a[v] -= ag; if( node[pos[v]].cap == 0 ) u = pre[v]; } } } else if( u != s ) // 如果u ！= s 那么这条路走不通的话，从u的上一个节点继续找。 { lev[u] = INT_MAX; // 相当于从层次图里删除这个节点。 u = pre[u]; } else // 如果从源点找不到增广路，就结束咧。 break; } } return flow; } void Add(int u,int v,int len) { node[cou].from = u; node[cou].to = v; node[cou].cap = len; node[cou].next = net[u]; net[u] = cou++; node[cou].from = v; node[cou].to = u; node[cou].cap = 0; node[cou].next = net[v]; net[v] = cou++; } int main() { char ch; int from,to,len,ans; while( ~scanf("%d%d%d%d",&n,&np,&nc,&m) ) { init(); while( m-- ) { scanf(" (%d,%d)%d",&from,&to,&len); Add(from,to,len); } while( np-- ) { scanf(" (%d)%d",&from,&len); Add(n+1,from,len); } while( nc-- ) { scanf(" (%d)%d",&from,&len); Add(from,n+2,len); } ans = Dinic(n+1,n+2);; printf("%d/n",ans); } return 0; }
