Description

XWW是個影響力很大的人，他有很多的追隨者。這些追隨者都想要加入XWW教成為XWW的教徒。但是這并不容易，需要通過XWW的考核。
XWW給你出了這么一個難題：XWW給你一個N*N的正實數矩陣A，滿足XWW性。
稱一個N*N的矩陣滿足XWW性當且僅當：（1）A[N][N]=0；（2）矩陣中每行的最后一個元素等于該行前N-1個數的和；（3）矩陣中每列的最后一個元素等于該列前N-1個數的和。
現在你要給A中的數進行取整操作（可以是上取整或者下取整），使得最后的A矩陣仍然滿足XWW性。同時XWW還要求A中的元素之和盡量大。

Input

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

Output

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

考慮把每行，每列均視為一個點

#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<functional> #include<iostream> #include<cmath> #include<cctype> #include<ctime> using namespace std; #define For(i,n) for(int i=1;i<=n;i++) #define Fork(i,k,n) for(int i=k;i<=n;i++) #define Rep(i,n) for(int i=0;i<n;i++) #define ForD(i,n) for(int i=n;i;i--) #define RepD(i,n) for(int i=n;i>=0;i--) #define Forp(x) for(int p=pre[x];p;p=next[p]) #define Forpiter(x) for(int &p=iter[x];p;p=next[p]) #define Lson (x<<1) #define Rson ((x<<1)+1) #define MEM(a) memset(a,0,sizeof(a)); #define MEMi(a) memset(a,128,sizeof(a)); #define INF (2139062143) #define F (100000007) #define MAXN (200+10) #define MAXM ((10000+200)*5+10) #define MAXAi (35000) #define eps (1e-3) long long mul(long long a,long long b){return (a*b)%F;} long long add(long long a,long long b){return (a+b)%F;} long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;} typedef long long ll; class Cost_Flow { public: int n,s,t; int q[MAXM]; int edge[MAXM],next[MAXM],pre[MAXN],weight[MAXM],size; int cost[MAXM]; void addedge(int u,int v,int w,int c) { edge[++size]=v; weight[size]=w; cost[size]=c; next[size]=pre[u]; pre[u]=size; } void addedge2(int u,int v,int w,int c){addedge(u,v,w,c),addedge(v,u,0,-c);} bool b[MAXN]; int d[MAXN]; int pr[MAXN],ed[MAXN]; bool SPFA(int s,int t) { For(i,n) d[i]=INF,b[i]=0; d[q[1]=s]=0;b[s]=1; int head=1,tail=1; while (head<=tail) { int now=q[head++]; Forp(now) { int &v=edge[p]; if (weight[p]&&d[now]+cost[p]<d[v]) { d[v]=d[now]+cost[p]; if (!b[v]) b[v]=1,q[++tail]=v; pr[v]=now,ed[v]=p; } } b[now]=0; } return d[t]!=INF; } int totcost,maxflow; int CostFlow(int s,int t) { maxflow=0;while (SPFA(s,t)) { int flow=INF; for(int x=t;x^s;x=pr[x]) flow=min(flow,weight[ed[x]]); totcost+=flow*d[t]; maxflow+=flow; for(int x=t;x^s;x=pr[x]) weight[ed[x]]-=flow,weight[ed[x]^1]+=flow; } // cout<<maxflow<<endl;return totcost; } void mem(int n,int t) { (*this).n=n; size=1; totcost=0; MEM(pre) MEM(next) } }S1; int read() {int x=0,f=1; char ch=getchar();while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}return x*f; } int n; double a[MAXN][MAXN]; int in[MAXN]; int main() { // freopen("bzoj3698.in","r",stdin); // freopen(".out","w",stdout);n=read();For(i,n) For(j,n) scanf("%lf",&a[i][j]);int s=2*n+1,t=s+1,S=t+1,T=S+1;S1.mem(T,T);MEM(in) For(i,n-1) {in[i]+=(int)a[i][n]; in[s]-=(int)a[i][n];in[i+n]-=(int)a[n][i]; in[t]+=(int)a[n][i];if (fabs(a[i][n]-double((int)a[i][n])>eps)) S1.addedge2(s,i,1,0);if (fabs(a[n][i]-double((int)a[n][i])>eps)) S1.addedge2(i+n,t,1,0);} For(i,n-1)For(j,n-1) {in[i]-=int(a[i][j]);in[j+n]+=(int)(a[i][j]);if (fabs(a[i][j]-double((int)a[i][j])>eps)) S1.addedge2(i,j+n,1,0);} S1.addedge2(t,s,INF,0);int mflow=0;For(i,t) {if (in[i]>0) S1.addedge2(S,i,in[i],0),mflow+=in[i];if (in[i]<0) S1.addedge2(i,T,-in[i],0);} S1.CostFlow(S,T); if (S1.maxflow!=mflow) puts("No");else {S1.CostFlow(s,t);cout<<S1.maxflow*3<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的BZOJ 3698(XWW的难题-上下界网络流+经典建模)的全部內容，希望文章能夠幫你解決所遇到的問題。

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