F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:祝各位Oier新年快乐,Rp++!
大视野在线测评-欢迎您
[ New Thread ]
Problem 1458 >> 为什么最大流可过
770780079 @ 2017-12-25 11:44:22
[ Quote ] [ Edit ] [ Delete ] 1#
RT,我按行列匹配,从源点到行建边,从列到汇点建边,二分从源点直接到列的流量.
770780079 @ 2017-12-25 11:45:28
[ Quote ] [ Edit ] [ Delete ] 2#
int totL,totC;
bool ck(int ans){
S=n+m+1;T=S+2;
cnt=1;for(int i=1;i<=T;++i)head[i]=0;
rep(n)in(S,i,L[i]);
rep(m)in(S+1,i+n,inf),in(i+n,T,C[i]);
in(S,S+1,ans);
rep1(n,m)if(!can[i][j])in(i,j+n,1);
int ans1=0;
while(bfs())ans1+=dinic();
return ans1==totC;
}

int main(){
scanf("%d%d%d",&n,&m,&k);
rep(n)scanf("%d",&L[i]);
rep(m)scanf("%d",&C[i]);
rep(k){
int x,y;scanf("%d%d",&x,&y);
can[x][y]=1;
}
rep(n){
int cnt=0;
for(int j=1;j<=m;++j)cnt+=!can[i][j];
if(cnt<L[i])return 0*printf("JIONG!\n");
}
rep(m){
int cnt=0;
for(int j=1;j<=n;++j)cnt+=!can[j][i];
if(cnt<C[i])return 0*printf("JIONG!\n");
}
rep(n)totL+=L[i];
rep(m)totC+=C[i];
int l=0,r=n*m-k-totL;
while(l!=r){
int mid=l+r>>1;
if(ck(mid))r=mid;
else l=mid+1;
}
printf("%d\n",l+totL);
}
Karen @ 2017-12-25 13:16:13
[ Quote ] [ Edit ] [ Delete ] 3#
orz IOIAKer ST
pb0207 @ 2017-12-25 17:59:56
[ Quote ] [ Edit ] [ Delete ] 4#
orz IOIAKer ST
770780O79 @ 2017-12-25 18:04:08
[ Quote ] [ Edit ] [ Delete ] 5#
Orz 我的人怎么这么少啊
770780079 @ 2017-12-25 19:18:51
[ Quote ] [ Edit ] [ Delete ] 6#
.......................
[Top] [Previous Page] [Next Page]

HOME Back