上下界最大流

好久沒寫上下界的網絡流了，趕快復習一遍。對于這道題建圖不難，就是把行、列當成點，一個連S，一個連T。一個格子當成行到列的邊，上下取整當成上下界即可。

先說一下上下界可行流怎么搞。我們只要考慮把下界填平使得圖流量平衡即可。對于入下界大于出下界的點，因為要填平下界，而出去的流量少了，因此要給它補充一些流量，S’向它連差值的邊即可，反之連T’。

然后考慮上下界最大流怎么搞。一個辦法是按照論文里說的二分出一個答案，T->S的連這個權值的邊，然后判有沒有可行流。正確性易證，但是復雜度帶一個log。

一個更高效的算法是先找出原圖的可行流，然后直接從S到T再跑最大流即可得到答案。因為可行流保證了在有下界情況下的流量平衡，因此暴力增廣是對的。

最后每一條邊的下界+流量就是這條邊在原圖的真實流量。

然后這題有點坑，矩陣里可以有負數，直接用int來取整是向0取整的!……因此要用floor和ceil，坑了半天好氣啊……

#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define N 222 using namespace std; namespace runzhe2000 {typedef double db;const int INF = 1<<29;int S, T, SS, TT, s, t, q[N], level[N];int ecnt = 1, n, nn, last[N], cur[N], deg[N], val[N][N];db a[N][N];struct edge{int next, to, flow;}e[N*N<<2];void addedge(int a, int b, int down, int up){ // printf("%d %d %d %d\n",a,b,down,up); // printf("%d %d %d\n",a,b,up-down);deg[a] -= down; deg[b] += down;e[++ecnt] = (edge){last[a], b, up-down};last[a] = ecnt;e[++ecnt] = (edge){last[b], a, 0};last[b] = ecnt;}int bfs(){memset(level,0,sizeof(level)); level[q[0] = s] = 1;for(int head=0, tail=1; head<tail; head++){int x = q[head];for(int i = last[x]; i; i = e[i].next){int y = e[i].to;if(!level[y] && e[i].flow){level[y] = level[x] + 1, q[tail++] = y;if(y == t) return 1;}}}return 0;}int dfs(int x, int flow){if(x == t) return flow; int use = 0;for(int &i = cur[x]; i; i = e[i].next){int y = e[i].to; if(level[x]+1 != level[y]) continue;int w = dfs(y, min(flow-use, e[i].flow));e[i].flow -= w; e[i^1].flow += w; use += w;if(use == flow) return use;}return use;}int dinic(){int r = 0; for(; bfs(); memcpy(cur, last, sizeof(cur)), r += dfs(s, INF)); return r;}void main(){scanf("%d",&n); S = n+n+1, T = n+n+2, SS = n+n+3, TT = n+n+4; nn = n+n+4;for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) scanf("%lf",&a[i][j]);for(int i = 1; i < n; i++) for(int j = 1; j < n; j++) addedge(i, j+n, (int)floor(a[i][j]), (int)ceil(a[i][j]));for(int i = 1; i < n; i++) addedge(S, i, (int)floor(a[i][n]), (int)ceil(a[i][n])), addedge(i+n, T, (int)floor(a[n][i]), (int)ceil(a[n][i]));for(int i = 1; i <= nn; i++) deg[i] > 0 ? addedge(SS, i, 0, deg[i]) : addedge(i, TT, 0, -deg[i]);int v = 0; for(int i = last[SS]; i; i = e[i].next) v += e[i].flow;addedge(T, S, 0, INF); s = SS, t = TT; if(dinic() != v) return (void)puts("No");for(int i = last[S]; i; i = e[i].next) if(e[i].to == T) e[i].flow = e[i^1].flow = 0;//int ans = 0; s = S, t = T; dinic();for(int i = 1; i < n; i++)for(int j = last[i]; j; j = e[j].next) if(n < e[j].to && e[j].to <= n+n)ans += (int)floor(a[i][e[j].to-n]) + e[j^1].flow, val[i][e[j].to - n] = e[j^1].flow;printf("%d\n",ans*3);} } int main() {runzhe2000::main(); }

總結

以上是生活随笔為你收集整理的BZOJ 3698 XWW的难题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。