XWW給你一個N*N的正實數矩陣A，滿足XWW性。
稱一個N*N的矩陣滿足XWW性當且僅當：（1）A[N][N]=0；（2）矩陣中每行的最后一個元素等于該行前N-1個數的和；（3）矩陣中每列的最后一個元素等于該列前N-1個數的和。
現在你要給A中的數進行取整操作（可以是上取整或者下取整），使得最后的A矩陣仍然滿足XWW性。同時XWW還要求A中的元素之和盡量大。

第一行一個整數N,N ≤ 100。
接下來N行每行包含N個絕對值小于等于1000的實數，最多一位小數

輸出一行，即取整后A矩陣的元素之和的最大值。無解輸出No。

4
3.1 6.8 7.3 17.2
9.6 2.4 0.7 12.7
3.6 1.2 6.5 11.3
16.3 10.4 14.5 0 129

題解

上下界網絡流的最大流模板題

有一個小細節：當遇到3.0這種情況時，它無論上取整還是下取整都是3

以為可以A了

然后一直過不了樣例

和xmy大佬調了30min

因為有一個極其隱蔽的錯誤：

SAP在寫gap優化的時候要把點數預留準確！！！！

ans=cap[cnt];S=ss;T=tt;//fir[ss]=nxt[fir[ss]];//fir[tt]=nxt[fir[tt]];cap[cnt]=cap[cnt^1]=0;f();ans+=flow;printf("%d",3*ans);

因為這一段中沒有把原來的S和T刪掉，所以有可能還會走到原來的源匯點

如果此時點數已經更新為了2*n+2，那么可能導致gap[0]直接減小到為0（因為你可能刪2*n+4個點）

所以，要么重新建圖，要么把點數預留為原來的點數

（以后再也不用 T 來表示圖中點的數目了。。。）

一定要在外面用一個sz來存

?

代碼：

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int n; #define N 505 #define M 400005 const int INF=0x3f3f3f3f; int fir[N],to[M],nxt[M],cap[M],cnt; int ind[N],oud[N],sum; void adde(int a,int b,int l,int r) {to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;cap[cnt]=r-l;to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;cap[cnt]=0;ind[b]+=l;oud[a]+=l; } int S,T,flow,d[N],vd[N]; int sz; int sap(int u,int aug) {if(u==T) return aug;int ret=0,tmp,mind=sz-1;for(int v,p=fir[u];p;p=nxt[p]){v=to[p];if(cap[p]>0){if(d[u]==d[v]+1){tmp=sap(v,min(cap[p],aug));aug-=tmp;cap[p]-=tmp;ret+=tmp;cap[p^1]+=tmp;if(d[S]>=sz) return ret;if(aug==0) break;}mind=min(mind,d[v]);}}if(ret==0){vd[d[u]]--;if(!vd[d[u]])d[S]=sz;d[u]=mind+1;vd[d[u]]++;}return ret; } void f() {memset(d,0,sizeof(d));memset(vd,0,sizeof(vd));sz=2*n+4;vd[0]=sz;flow=0;while(d[S]<sz)flow+=sap(S,INF); } int l[N][N],r[N][N]; int main() {cnt=1;int i,j;float x;scanf("%d",&n);for(i=1;i<=n;i++)for(j=1;j<=n;j++){scanf("%f",&x);l[i][j]=int(floor(x));r[i][j]=int(ceil(x));}n--;int ss=2*n+1,tt=2*n+2;S=2*n+3;T=2*n+4;for(i=1;i<=n;i++){adde(ss,i,l[i][n+1],r[i][n+1]);adde(i+n,tt,l[n+1][i],r[n+1][i]);for(j=1;j<=n;j++)adde(i,j+n,l[i][j],r[i][j]);}for(i=1;i<=2*n+2;i++){if(ind[i]>oud[i]){adde(S,i,0,ind[i]-oud[i]);sum+=ind[i]-oud[i];}if(ind[i]<oud[i]) adde(i,T,0,oud[i]-ind[i]);}adde(tt,ss,0,INF);//printf("%d\n",cnt);int ans=0;f();if(flow!=sum){printf("No");return 0;}ans=cap[cnt];S=ss;T=tt;//fir[ss]=nxt[fir[ss]];//fir[tt]=nxt[fir[tt]];cap[cnt]=cap[cnt^1]=0;f();ans+=flow;printf("%d",3*ans); }

?

總結

以上是生活随笔為你收集整理的BZOJ3698 XWW的难题（上下界网络流+gap优化的细节处理）的全部內容，希望文章能夠幫你解決所遇到的問題。

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