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优化的细节处理）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。