3698: XWW的难题
Time Limit: 10 Sec
Memory Limit: 128 MB
[
Submit][
Status][
Discuss]
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
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;
}
