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
Solution
把每行每列当做一个点，那么每条边可以抽象为一条边。
建立源点汇点，对于每行(s)向这个点连边，流量下界为(lfloor x floor)，上界为(lceil x ceil)，对于每列同理，向(t)连边。
对于每个点，设当前点为(i)行(j)列，那么(i)行向(j)列连边，上界下界同理。
那么如果没有可行流就无解，否则答案就是最大流(*3)，这个是因为每个点的权值都被算了三次。
注意可行流不是(dinic)跑出来的流量！！我被这里坑了好久。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
#define lf double
#define ll long long
const int maxn = 2e5+10;
const int inf = 1e9;
const lf eps = 1e-8;
double a[102][102];
int head[maxn],tot=1,dis[maxn],r[maxn],ban[maxn],SIZE,n;
struct edge{int to,nxt,w;}e[maxn<<1];
void add2(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}
void add(int u,int v,int w) {add2(u,v,w),add2(v,u,0);}
void ins(int u,int v,int up,int down) {r[u]-=down,r[v]+=down,add(u,v,up-down);}
#define p(x,y) ((x)*(n-1)+(y))
int bfs(int s,int t) {
memset(dis,-1,SIZE);
queue<int > q;q.push(s);dis[s]=0;
while(!q.empty()) {
int now=q.front();q.pop();
for(int v,i=head[now];i;i=e[i].nxt)
if(e[i].w>0&&dis[v=e[i].to]<0&&!ban[i]) {
dis[v]=dis[now]+1;
if(v==t) return 1;
q.push(v);
}
}return 0;
}
int dfs(int x,int t,int f) {
if(x==t) return f;
int used=0;
for(int v,i=head[x];i;i=e[i].nxt)
if(e[i].w>0&&dis[v=e[i].to]==dis[x]+1&&(!ban[i])) {
int d=dfs(e[i].to,t,min(f-used,e[i].w));
if(d>0) e[i].w-=d,e[i^1].w+=d,used+=d;
if(used==f) break;
}
if(!used) dis[x]=-1;
return used;
}
int dinic(int s,int t) {
int flow=0;
while(bfs(s,t)) flow+=dfs(s,t,inf);
return flow;
}
int main() {
read(n);int ans=0;
int s=n*2+1,t=s+1,S=t+1,T=S+1;SIZE=(T+2)*4;
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-1;i++)
for(int j=1;j<=n-1;j++)
ins(i,j+n,ceil(a[i][j]),trunc(a[i][j]));
for(int i=1;i<=n-1;i++) {
ins(s,i,ceil(a[i][n]),trunc(a[i][n]));
ins(i+n,t,ceil(a[n][i]),trunc(a[n][i]));
}
int res=tot+1,sum=0;
add(t,s,inf);
for(int i=1;i<=n*2+2;i++)
if(r[i]>0) add(S,i,r[i]),sum+=r[i];
else if(r[i]) add(i,T,-r[i]);
ans=dinic(S,T);
if(ans!=sum) return puts("NO"),0;ans=e[res^1].w;
for(int i=res;i<=tot;i++) ban[i]=1;
write((ans+dinic(s,t))*3);
return 0;
}