3698: XWW的难题
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 354 Solved: 178
[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
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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=;
const int M=1e5+;
struct edge{int v,next,cap;}e[M];int tot=,head[N];
int n,S,T,SS,TT,res,sum,in[N],dis[N],q[M];
double a[N][N];
inline void add(int x,int y,int z){
e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;
e[++tot].v=x;e[tot].cap=;e[tot].next=head[y];head[y]=tot;
}
bool bfs(int S,int T){
memset(dis,-,sizeof dis);
int h=,t=;q[t]=S;dis[S]=;
while(h!=t){
int x=q[++h];
for(int i=head[x];i;i=e[i].next){
if(e[i].cap&&dis[e[i].v]==-){
dis[e[i].v]=dis[x]+;
if(e[i].v==T) return ;
q[++t]=e[i].v;
}
}
}
return ;
}
int dfs(int x,int T,int f){
if(x==T) return f;
int used=,t;
for(int i=head[x];i;i=e[i].next){
if(e[i].cap&&dis[e[i].v]==dis[x]+){
t=dfs(e[i].v,T,min(e[i].cap,f));
e[i].cap-=t;e[i^].cap+=t;
used+=t;f-=t;
if(!f) return used;
}
}
if(!used) dis[x]=-;
return used;
}
void dinic(int S,int T){
res=;
while(bfs(S,T)) res+=dfs(S,T,2e9);
}
void mapping(){
scanf("%d",&n);
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%lf",&a[i][j]);
}
}
S=n<<|;T=S+;SS=S+;TT=S+;
for(int i=;i<n;i++){
if(a[i][n]!=(int)a[i][n]) add(S,i,);
in[S]-=(int)a[i][n];in[i]+=(int)a[i][n];
}
for(int i=;i<n;i++){
if(a[n][i]!=(int)a[n][i]) add(i+n,T,);
in[i+n]-=(int)a[n][i];in[T]+=(int)a[n][i];
}
for(int i=;i<n;i++){
for(int j=;j<n;j++){
if(a[i][j]!=(int)a[i][j]) add(i,j+n,);
in[i]-=(int)a[i][j];in[j+n]+=(int)a[i][j];
}
}
for(int i=;i<=TT;i++){
if(in[i]>) add(SS,i,in[i]),sum+=in[i];
if(in[i]<) add(i,TT,-in[i]);
}
add(T,S,2e9);
}
int main(){
mapping();
dinic(SS,TT);
if(res!=sum){puts("No");return ;}
dinic(S,T);
printf("%d\n",res*);
return ;
}