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。

Sample Input

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

Sample Output

129

HINT

【數據規模與約定】

有10組數據，n的大小分別為10,20,30…100。

【樣例說明】

樣例中取整后滿足XWW性的和最大的矩陣為：

3 7 8 18

10 3 0 13

4 1 7 12

17 11 15 0

題解
有上下界的網絡流。
學習文章：http://blog.csdn.net/clove_unique/article/details/54884437

代碼

#include<cstdio> #include<iostream> #include<queue> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } queue<int>q; int S,T,SS,TT; int n,cnt=1,tot,ans; int dis[205],in[205],cur[205]; double a[205][205]; int Head[205],Next[100005],ret[100005],len[100005]; void ins(int u,int v,int w) {ret[++cnt]=v;Next[cnt]=Head[u];Head[u]=cnt;len[cnt]=w; } void insert(int u,int v,int w) {ins(u,v,w);ins(v,u,0);} void build() {for (int i=1;i<n;i++){if (a[i][n]!=(int)a[i][n])insert(S,i,1);in[S]-=(int)a[i][n];in[i]+=(int)a[i][n];}for (int i=1;i<n;i++){if (a[n][i]!=(int)a[n][i])insert(i+n,T,1);in[i+n]-=(int)a[n][i];in[T]+=(int)a[n][i];}for (int i=1;i<n;i++)for (int j=1;j<n;j++){if (a[i][j]!=(int)a[i][j])insert(i,j+n,1);in[i]-=(int)a[i][j];in[j+n]+=(int)a[i][j];}for (int i=1;i<=TT;i++)if (in[i]>0){tot+=in[i];insert(SS,i,in[i]);}else insert(i,TT,-in[i]); } bool bfs(int x,int y) {for (int i=1;i<=TT;i++) dis[i]=-1;dis[x]=0;q.push(x);while (!q.empty()){int now=q.front();q.pop();for (int i=Head[now];i;i=Next[i]){if (len[i]&&dis[ret[i]]==-1){dis[ret[i]]=dis[now]+1;q.push(ret[i]);}}}return dis[y]!=-1; } int dfs(int x,int y,int aug) {if (x==y||aug==0) return aug;int flow=0;for (int i=cur[x];i;i=Next[i])if (dis[ret[i]]==dis[x]+1){int t=dfs(ret[i],y,min(aug-flow,len[i]));flow+=t;len[i]-=t;len[i^1]+=t;if (len[i]) cur[x]=i;if (flow==aug) return flow;}if (flow==0) dis[x]=-1;return flow; } void dinic(int x,int y) {while(bfs(x,y)){for(int i=1;i<=TT;i++)cur[i]=Head[i];ans+=dfs(x,y,inf);} } int main() {n=read();S=2*n+1;T=S+1;SS=T+1;TT=SS+1;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)scanf("%lf",&a[i][j]);build();insert(T,S,inf);dinic(SS,TT);if (tot!=ans)return puts("No"),0;ans=0;dinic(S,T);printf("%d",ans*3);return 0; }

總結

以上是生活随笔為你收集整理的【bzoj3698】XWW的难题 有源汇上下界网络流最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

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