@OceanEye6年前
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
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
HINT
【数据规模与约定】
有10组数据,n的大小分别为10,20,30…100。
【样例说明】
样例中取整后满足XWW性的和最大的矩阵为:
3 7 8 18
10 3 0 13
4 1 7 12
17 11 15 0
朴素的建图,只是跑的网络流模式变了
然后就可以随便艹了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <cmath> #include <vector> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') #define For(i,l,r) for(int i=l;i<=r;i++) char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define EE 80000 #define N 300 #define source 0 #define sink N-1 #define source_ N-2 #define sink_ N-3 struct Tedge { int to,flow; }edge[EE]; int e_tot,nxt[EE],fst[N]; #define E edge[i] #define FLOW E.flow #define TO E.to #define NXT nxt[i] #define calc(i) (n+i) void add_e(int from,int to,int flow) { static int &i=e_tot; TO=to; FLOW=flow; NXT=fst[from]; fst[from]=i++; TO=from; FLOW=0; NXT=fst[to]; fst[to]=i++; } double a[N][N]; int imp[N],in[N]; int n,S,T; void init() { int _; memset(fst,-1,sizeof(fst)); read(n); For(i,1,n) for(int j=1;j<=n;j++) scanf("%lf",&a[i][j]); For(i,1,n-1) for(int j=1;j<n;j++) { _=(int)floor(a[i][j]); if(ceil(a[i][j])!=_) add_e(i,calc(j),1); in[i]-=_; in[calc(j)]+=_; } For(i,1,n-1) { _=floor(a[i][n]); in[i]+=_; in[source]-=_; if(ceil(a[i][n])!=_) add_e(source,i,1); } For(i,1,n-1) { _=floor(a[n][i]); in[sink]+=_; in[calc(i)]-=_; if(ceil(a[n][i])!=_) add_e(calc(i),sink,1); } add_e(sink,source,INF); For(i,0,N-1) if(in[i]) { in[i]>0?add_e(source_,i,in[i]):add_e(i,sink_,-in[i]); imp[i]=e_tot-2; } } int cnt[N],d[N]; bool bfs() { memset(d,0,sizeof(d)); memset(cnt,0,sizeof(cnt)); static int queue[65540],x; static unsigned short int he=0,ta=0; queue[++he]=T; d[T]=1; while(he!=ta) { x=queue[++ta]; cnt[d[x]]++; for(int i=fst[x];~i;i=NXT) if(!d[TO]&&edge[i^1].flow) { d[TO]=d[x]+1; queue[++he]=TO; } } return d[S]; } void cp(int &x,int y) { x>y?x=y:x; } int p[N]; int Augment() { static int node,c,i; node=T; c=INF; while(node!=S) { i=p[node]; cp(c,FLOW); node=edge[i^1].to; } node=T; while(node!=S) { i=p[node]; FLOW-=c; i^=1; FLOW+=c; node=TO; } return c; } int ISAP() { static int node,cur[N],ret; static bool flag; if(!bfs()) return 0; node=S; ret=0; for(int i=0;i<N;i++) cur[i]=fst[i]; while(d[S]<n*2+5) { if(node==T) { ret+=Augment(); node=S; } flag=false; for(int i=cur[node];~i;i=NXT) if(d[TO]==d[node]-1&&FLOW) { p[TO]=i; cur[node]=i; node=TO; flag=true; break; } if(flag) continue; int M=N-1; if(!--cnt[d[node]]) break; for(int i=fst[node];~i;i=NXT) if(FLOW) cp(M,d[TO]+1); cnt[d[node]=M]++; cur[node]=fst[node]; node==S?node:node=edge[p[node]^1].to; } return ret; } bool check() { For(i,0,N-1) if(imp[i]) if(edge[imp[i]].flow) return false; return true; } int main() { init(); S=source_,T=sink_; ISAP(); // printf("%d\n",ISAP()); if(!check()) { puts("-1"); return 0; } S=source,T=sink; printf("%d\n",ISAP()*3); return 0; } |