1 /* 2 題意：無源無匯，并且每條邊的容量有上下界限的網絡流問題！既然無源無匯，那么素有的節點都應該滿足“入流==出流”！ 3 輸出每一條邊的流量，使得滿足上面的條件。（如果u->v有流量，那么v->u就不會有流量） 4 5 思路：如果增加了源點s和匯點t，對于u->v（下限為l， 上限為f） 將這一條邊拆成3條，s->v(容量為l)， u->v(容量為f-l) 6 u->t(容量為l)這樣就變成了每一個點的流入或者流出的流量至少是b！然后從s->t走一遍最大流，如果所有的附件邊都已經 7 滿載，則就是所有s->v的邊和u->t的邊（或者只判斷其中一者就可以），那么就存在答案！ 8 */ 9 #include<iostream> 10 #include<cstdio> 11 #include<cstring> 12 #include<algorithm> 13 #include<vector> 14 #include<queue> 15 #define INF 0x3f3f3f3f 16 #define N 205 17 #define M 500000 18 using namespace std; 19 20 struct EDGE{ 21 int v, cap, tot, nt, b; 22 EDGE(){}; 23 EDGE(int v, int cap, int nt, int b) : v(v), cap(cap), nt(nt), b(b), tot(cap){} 24 }; 25 26 EDGE edge[M]; 27 int n, m; 28 int first[N]; 29 int pre[N], d[N]; 30 int sz; 31 int s, t; 32 int full, fout; 33 34 void addEdge(int u, int v, int b, int cap){ 35 edge[sz] = (EDGE(v, cap, first[u],b)); 36 first[u] = sz++; 37 edge[sz] = (EDGE(u, 0, first[v], 0)); 38 first[v] = sz++; 39 40 edge[sz] = (EDGE(v, b, first[s], 0)); 41 first[s] = sz++; 42 edge[sz] = (EDGE(s, 0, first[v], 0)); 43 first[v] = sz++; 44 45 edge[sz] = (EDGE(t, b, first[u], 0)); 46 full += b; 47 first[u] = sz++; 48 edge[sz] = (EDGE(u, 0, first[t], 0)); 49 first[t] = sz++; 50 } 51 52 bool bfs(){ 53 queue<int>q; 54 memset(d, 0, sizeof(d)); 55 d[s] = 1; 56 q.push(s); 57 while(!q.empty()){ 58 int u = q.front(); q.pop(); 59 for(int i = first[u]; ~i; i = edge[i].nt){ 60 int v = edge[i].v; 61 if(!d[v] && edge[i].cap >0){ 62 d[v] = d[u] + 1; 63 q.push(v); 64 } 65 } 66 } 67 if(d[t] == 0) return false; 68 return true; 69 } 70 71 int dfs(int u, int totf){ 72 int ff; 73 if( u == t) return totf; 74 int flow = 0; 75 for(int i = first[u]; ~i && totf > flow; i = edge[i].nt){ 76 int v = edge[i].v; 77 int cap = edge[i].cap; 78 //流入u節點的當前總的流量為totf，可以得到 u->v1, u->v2, u->v3....這些路徑上的最大流的和為flow+=f（u->vi） 79 //f(u->vi)表示u節點沿著vi節點方向的路徑上的最大流；如果u->vi+1的容量為wi+1，那么u->vi+1所允許流過的最大 80 //的流量就是 min(totf - cost, wi+1)了！ 81 if(d[v] == d[u] + 1 && cap > 0 ){ 82 ff = dfs(v, min(totf - flow, cap)); 83 if(ff){ 84 edge[i].cap -= ff; 85 edge[i^1].cap += ff; 86 flow += ff; 87 } 88 else 89 d[v] = -1;//表示v這個點無法在繼續增廣下去了 90 } 91 } 92 return flow;//返回從u節點向外流出的最大流量！ 93 } 94 95 bool Dinic(){ 96 while(bfs()) 97 fout += dfs(0, INF);//這一塊沒想到寫成while（dfs（））會超時.... 98 99 if( fout != full) return false; 100 return true; 101 } 102 103 int main(){ 104 105 scanf("%d%d", &n, &m); 106 memset(first, -1, sizeof(first)); 107 sz = 0; 108 fout = full = 0; 109 s = 0; t = n+1; 110 int u, v, l, f; 111 for(int i = 1; i <= m; ++i){ 112 scanf("%d%d%d%d", &u, &v, &l, &f); 113 addEdge(u, v, l, f-l); 114 } 115 if(!Dinic()){ 116 printf("NO\n"); 117 return 0; 118 } 119 printf("YES\n"); 120 for(int i = 1; i <= m; ++i){ 121 int j = (i-1)*6; 122 printf("%d\n", edge[j].tot - edge[j].cap + edge[j].b);//輸出這條邊實際流過的流量+下限 123 } 124 125 return 0; 126 }
?
..doc)
)
)
)
)
描述)
