[文章目录]
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中的元素之和尽量大。n<=100
有上下界最大流，构造二分图。判断是否存在可行流，再跑最大流。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int n,ans,sum,s,t,ss,tt,S,T;
int head[2100],to[40000],nxt[40000],f[40000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
queue<int>q;
int dis[2100];
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
int rd[2100],cd[2100];
int main()
{
scanf("%d",&n); double x;
ss=(n<<1)+1; tt=ss+1; S=tt+1; T=S+1;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
scanf("%lf",&x);
if(i==n&&j!=n)
{
if(x-(int)x>1e-2) add(j+n,tt,1);
rd[tt]+=(int)x;
cd[j+n]+=(int)x;
}
if(i!=n&&j==n)
{
if(x-(int)x>1e-2) add(ss,i,1);
rd[i]+=(int)x;
cd[ss]+=(int)x;
}
if(i!=n&&j!=n)
{
if(x-(int)x>1e-2) add(i,j+n,1);
rd[j+n]+=(int)x;
cd[i]+=(int)x;
}
}
if(x>1e-2) {puts("No"); return 0;}
for(int i=1;i<=(n<<1);++i)
{
add(S,i,rd[i]); sum+=rd[i];
add(i,T,cd[i]);
}
add(S,ss,rd[ss]); add(ss,T,cd[ss]);
add(S,tt,rd[tt]); add(tt,T,cd[tt]);
sum+=rd[ss]+rd[tt];
add(tt,ss,inf);
s=S; t=T; while(bfs()) sum-=dinic(s,inf);
if(sum) {puts("No"); return 0;}
for(int i=head[tt];i;i=nxt[i]) if(to[i]==ss) ans+=f[i^1],f[i]=f[i^1]=0;
s=ss; t=tt; while(bfs()) ans+=dinic(s,inf);
printf("%d",ans*3);
return 0;
}