題目鏈接: https://www.lydsy.com/JudgeOnline/problem.php?id=2127

題解: 這道題就是傳說中的“解方程”法。（貌似也有類似于BZOJ 3894的做法，但是邊數比較多。）

以下設\(A_i\)為\(i\)選文的收益，\(B_i\)為\(i\)選理的收益，\(AA_{i,j}\)表示\(i,j\)同文的收益，\(BB_{i,j}\)表示\(i,j\)同理的收益。

首先對于每個點\(i\), 從\(S\)向\(i\)連\(A_i\)，從\(i\)向\(T\)連\(B_i\)這個沒有問題。

然后考慮處理同文同理的代價。

考慮\(S,T,i,j\)共\(4\)個點之間可以連\(6\)條邊，設\(S\)到\(i\), \(i\)到\(T\), \(S\)到\(j\), \(j\)到\(T\), \(i\)到\(j\), \(j\)到\(i\)的容量分別為\(a,b,c,d,e,f\).

枚舉\(i,j\)選文理的四種情況可以列出四個方程。

若\(i\in S, j\in S\), 則割掉的邊是\(b\)和\(d\), 代價是兩人不可同理(science)(注意單人文理的代價已經在剛才算過了，所以不要再算！)可得\(b+d=BB_{i,j}\), 同理(reason)可得\(a+c=AA_{i,j}\).

若\(i\in S, j\in T\), 則割掉的邊是\(b,c,e\) (一定注意沒有\(f\)), 代價是二人不可同文或同理(science), 可得\(b+c+e=AA_{i,j}+BB_{i,j}\), 同理(reason)可得\(a+d+f=AA_{i,j}+BB_{i,j}\).

這樣我們列出了\(4\)個方程，給\(6\)個變量復制綽綽有余，可以隨便取值。但是注意也不能太隨便，比如不能出負數等等。一種比較好的取法是: \[a=c=\frac{AA_{i,j}}{2},b=d=\frac{BB_{i,j}}{2},e=f=\frac{AA_{i,j}+BB_{i,j}}{2}\]

最后合并起點終點均相同的邊來減少邊數，除以\(2\)可以先乘\(2\)再把答案除以\(2\)處理，避免出現小數。

好神仙啊……

代碼

#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std;const int INF = 4e8;namespace MaxFlow {const int N = 1e4+2;const int M = 6e4;struct Edge{int v,w,nxt,rev;} e[(M<<1)+3];int fe[N+3],te[N+3];int que[N+3];int dep[N+3];int n,en,s,t;void addedge(int u,int v,int w){en++; e[en].v = v; e[en].w = w;e[en].nxt = fe[u]; fe[u] = en; e[en].rev = en+1;en++; e[en].v = u; e[en].w = 0;e[en].nxt = fe[v]; fe[v] = en; e[en].rev = en-1;}bool bfs(){for(int i=1; i<=n; i++) dep[i] = 0;int head = 1,tail = 1; que[tail] = s; dep[s] = 1;while(head<=tail){int u = que[head]; head++;for(int i=fe[u]; i; i=e[i].nxt){if(dep[e[i].v]==0 && e[i].w>0){dep[e[i].v] = dep[u]+1;tail++; que[tail] = e[i].v;}}}return dep[t]!=0;}int dfs(int u,int cur){if(u==t) return cur;int rst = cur;for(int i=te[u]; i; i=e[i].nxt){if(dep[e[i].v]==dep[u]+1 && rst>0 && e[i].w>0){int flow = dfs(e[i].v,min(rst,e[i].w));if(flow>0){e[i].w -= flow; e[e[i].rev].w += flow; rst -= flow;if(e[i].w>0) te[u] = i;if(rst==0) return cur;}}}if(rst==cur) dep[u] = 0;return cur-rst;}int dinic(int _n,int _s,int _t){n = _n,s = _s,t = _t;int ret = 0;while(bfs()){for(int i=1; i<=n; i++) te[i] = fe[i];ret += dfs(s,INF);}return ret;} } using MaxFlow::addedge; using MaxFlow::dinic;const int N = 100; int a[N+3][N+3]; int b[N+3][N+3]; int aa1[N+3][N+3]; int aa2[N+3][N+3]; int bb1[N+3][N+3]; int bb2[N+3][N+3]; int n,m;int getid(int x,int y) {return (x-1)*m+y+2;}int main() {scanf("%d%d",&n,&m); int ans = 0;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++) scanf("%d",&a[i][j]),ans += a[i][j];}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++) scanf("%d",&b[i][j]),ans += b[i][j];}for(int i=1; i<n; i++){for(int j=1; j<=m; j++) scanf("%d",&aa1[i][j]),ans += aa1[i][j];}for(int i=1; i<n; i++){for(int j=1; j<=m; j++) scanf("%d",&bb1[i][j]),ans += bb1[i][j];}for(int i=1; i<=n; i++){for(int j=1; j<m; j++) scanf("%d",&aa2[i][j]),ans += aa2[i][j];}for(int i=1; i<=n; i++){for(int j=1; j<m; j++) scanf("%d",&bb2[i][j]),ans += bb2[i][j];}for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){int x = getid(i,j);addedge(1,x,(a[i][j]<<1)+aa1[i][j]+aa1[i-1][j]+aa2[i][j]+aa2[i][j-1]);addedge(x,2,(b[i][j]<<1)+bb1[i][j]+bb1[i-1][j]+bb2[i][j]+bb2[i][j-1]);if(i<n){int y = getid(i+1,j);addedge(x,y,aa1[i][j]+bb1[i][j]);addedge(y,x,aa1[i][j]+bb1[i][j]);}if(j<m){int y = getid(i,j+1);addedge(x,y,aa2[i][j]+bb2[i][j]);addedge(y,x,aa2[i][j]+bb2[i][j]);}}}int tmp = dinic(n*m+2,1,2);ans -= (tmp>>1);printf("%d\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 2127 happiness (最小割)的全部內容，希望文章能夠幫你解決所遇到的問題。

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