3698: XWW的難題

Time Limit:?10 Sec??Memory Limit:?128 MB
[Submit][Status][Discuss]

Description

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

Input

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

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

【數(shù)據(jù)規(guī)模與約定】

有10組數(shù)據(jù)，n的大小分別為10,20,30...100。

【樣例說明】

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

3 7 8 18

10 3 0 13

4 1 7 12

17 11 15 0

Source

原圖： S->i ? ?a[i][n],a[i][n]+1 i->T ? ?a[n][j],a[n][j]+1 i->j ? ? ?i->j ? a[i][j],a[i][j]+1 #include<iostream> #include<cstring> #include<cstdio> #define inf 0x7fffffff using namespace std; const int N = 205; int last[N],h[N],q[N],b[N],ans,cnt=1,T,S,SS,TT,n,cur[N],tot; double a[N][N]; struct Edge{int to,next,v; }e[200005]; void insert( int u, int v, int w ){e[++cnt].to = v; e[cnt].next = last[u]; e[cnt].v = w; last[u] = cnt;e[++cnt].to = u; e[cnt].next = last[v]; e[cnt].v = 0; last[v] = cnt; } bool bfs( int x, int y ){memset(h,-1,sizeof(h));int tail = 1, head = 0;q[0] = x; h[x] = 0;while( tail != head ){int now = q[head++];for( int i = last[now]; i; i = e[i].next )if( h[e[i].to] == -1 && e[i].v ){h[e[i].to] = h[now] + 1;q[tail++] = e[i].to;}}return h[y] != -1; } int dfs( int x, int f, int TTT ){int w,used=0;if( x == TTT ) return f;for( int i = cur[x]; i; i = e[i].next )if( h[e[i].to] == h[x] + 1 ){w = dfs(e[i].to,min(e[i].v,f-used),TTT);e[i].v -= w; e[i^1].v += w; used += w;if( e[i].v ) cur[x] = i; if( f == used ) return f;}if( !used ) h[x] = -1;return used; } void dinic( int x, int y ){while( bfs(x,y) ){for( int i = 1; i <= TT; i++ ) cur[i] = last[i];ans += dfs(x,inf,y);} } int main(){scanf("%d", &n);S = n*2+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]);for( int i = 1; i < n; i++ ){if( a[i][n] != (int)a[i][n] ) insert(S,i,1);b[S] -= (int)a[i][n]; b[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);b[i+n] -= (int)a[n][i]; b[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);b[i] -= (int)a[i][j]; b[j+n] += (int)a[i][j];}for( int i = 1; i <= TT; i++ )if( b[i] > 0 ){ tot += b[i]; insert( SS, i, b[i] ); }else insert( i, TT, -b[i] );insert(T,S,inf);dinic(SS,TT); //printf("%d\n", ans*3);if( tot != ans ) { printf("No"); return 0; }ans = 0; dinic(S,T); printf("%d\n", ans*3);return 0; }

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。