3698: XWW的难题

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 533  Solved: 275

[][][]

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

 

n行n列分别看成n个点,s为源点,t为汇点.

s向每一行i连(l[i][n],r[i][n])的边.

每一列i向t连(l[n][i],r[i][n])的边.

每一行i向每一行j连(l[i][j],r[i][j])的边.

求有源有汇有上下界的最大流.

最后答案要乘3.

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 using namespace std; 8 int n; 9 double a[105][105];10 int l[105][105],r[105][105];11 int s=0,t=999,S=1000,T=1001;12 int q[10005],dis[10005];13 struct edge {14 int to,next,f;15 }e[80050];16 int head[10000],cnt;17 void add(int u,int v,int w) {18 e[cnt].to=v;e[cnt].next=head[u];e[cnt].f=w;head[u]=cnt++;19 e[cnt].to=u;e[cnt].next=head[v];e[cnt].f=0;head[v]=cnt++;20 }21 bool bfs() {22 memset(dis,-57,sizeof(dis));23 int h=0,tail=1;24 q[h]=T;25 dis[T]=0;26 while(h!=tail) {27 int now=q[h++];if(h==10000) h=0;28 for(int i=head[now];i>=0;i=e[i].next) {29 if(dis[e[i].to]>-100000||!e[i^1].f) continue;30 dis[e[i].to]=dis[now]-1;31 q[tail++]=e[i].to;if(tail==10000) tail=0;32 } 33 }34 return dis[S]>=-100000;35 }36 int dfs(int now,int a) {37 int f=0,flow=0;38 if(now==T) return a;39 for(int i=head[now];i>=0;i=e[i].next) {40 int to=e[i].to;41 if(dis[to]==dis[now]+1&&e[i].f>0) {42 f=dfs(to,min(a,e[i].f));43 flow+=f;44 e[i].f-=f;45 e[i^1].f+=f;46 a-=f;47 if(a==0) break;48 }49 }50 return flow;51 }52 int dinic() {53 int ans=0;54 while(bfs()) {ans+=dfs(S,2147483647);}55 return ans;56 }57 int main() {58 memset(head,-1,sizeof(head));59 scanf("%d",&n);60 for(int i=1;i<=n;i++)61 for(int j=1;j<=n;j++) {62 scanf("%lf",&a[i][j]);63 l[i][j]=(int)a[i][j];64 if(a[i][j]==l[i][j]) r[i][j]=l[i][j];65 else r[i][j]=l[i][j]+1;66 }67 add(t,s,214748364);68 int sum=0;69 for(int i=1;i