bzoj 3504: [Cqoi2014]危桥

 #include<cstdio>
#include<iostream>
#include<cstring>
#define M 100009
#define inf 2139062143
using namespace std;
int n,a1,a2,an,b1,b2,bn,tot,cnt=,T,ans,head[M],d[M],q[*M],next[*M],u[*M],v[*M];
char ch[][];
bool bfs()
{
memset(d,,sizeof(int)*(T+));
int h=,t=;
q[]=;
d[]=;
for(;h<t;)
{
h++;
int p=q[h];
for(int i=head[p];i;i=next[i])
if(!d[u[i]]&&v[i])
{
d[u[i]]=d[p]+;
if(d[T])
return ;
t++;
q[t]=u[i];
}
}
return ;
}
int dinic(int s,int f)
{
if(s==T)
return f;
int rest=f;
for(int i=head[s];i&&rest;i=next[i])
if(v[i]&&d[u[i]]==d[s]+)
{
int now=dinic(u[i],min(rest,v[i]));
if(!now)
d[u[i]]=;
v[i]-=now;
v[i^]+=now;
rest-=now;
}
return f-rest;
}
void jia1(int a1,int a2,int a3)
{
cnt++;
next[cnt]=head[a1];
head[a1]=cnt;
u[cnt]=a2;
v[cnt]=a3;
return;
}
void jia(int a1,int a2,int a3)
{
jia1(a1,a2,a3);
jia1(a2,a1,);
return;
}
void build(int a1,int a2,int an,int b1,int b2,int bn)
{
T=n+;
cnt=;
memset(head,,sizeof(int)*(T+));
jia(,a1,*an);
jia(a2,T,*an);
jia(,b1,*bn);
jia(b2,T,*bn);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(ch[i][j]=='O')
jia(i,j,);
if(ch[i][j]=='N')
jia(i,j,inf);
}
return;
}
int main()
{
for(;scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)==;)
{
a1++;
a2++;
b1++;
b2++;
for(int i=;i<=n;i++)
scanf("%s",ch[i]+);
build(a1,a2,an,b1,b2,bn);
ans=;
for(;bfs();)
ans+=dinic(,inf);
if(ans==*an+*bn)
{
build(a1,a2,an,b2,b1,bn);
ans=;
for(;bfs();)
ans+=dinic(,inf);
if(ans==*an+*bn)
printf("Yes\n");
else
printf("No\n");
}
else
printf("No\n");}
return ;
}

网络流。

上一篇:懒人小工具:T4生成实体类Model,Insert,Select,Delete以及导出Excel的方法


下一篇:linux top 的用法