题面

传送门

思路

这道题中惟一的特别之处，就在于“危桥”这一个只能走两次的东西

我的第一想法是做一个dp，但是这道题只需要能不能走，也没有必要

网络流？貌似是个很好的选择

我们把所有边作为无向边加入图中，流量上限inf

危桥则作为上限2的无向边

从源点连边到a1b1，汇点连边到a2b2，流量都是2*an或2*bn，相当于一次把两遍走了

最后，只要看看最大流不是(2*an+2*bn)

然而有个问题，万一我们最终求得的最大流中，是a1流到b2、b1流到a2呢？

此时有一个好办法：我们把源点连边到a1b2，汇点连边到a2b1，如果还能满流，就OK了

具体为什么？自己画图理解一下即可~

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define inf 1e9

using namespace std;

int n,cnt=-1,first[110],dep[110],cur[110],a1,a2,an,b1,b2,bn;

struct edge{

	int to,next,w;

}a[10010];

inline void add(int u,int v,int w){

	a[++cnt]=(edge){v,first[u],w};first[u]=cnt;

	a[++cnt]=(edge){u,first[v],w};first[v]=cnt;

}

bool bfs(int s,int t){

	int q[110],head=0,tail=1,u,v,i;

	for(i=s;i<=t;i++) dep[i]=-1,cur[i]=first[i];

	q[0]=s;dep[s]=0;

	while(head<tail){

		u=q[head++];

		for(i=first[u];~i;i=a[i].next){

			v=a[i].to;

			if(~dep[v]||!a[i].w) continue;

			dep[v]=dep[u]+1;q[tail++]=v;

		}

	}

	return ~dep[t];

}

int dfs(int u,int t,int limit){

	if(u==t||!limit) return limit;

	int i,v,f,flow=0;

	for(i=first[u];~i;i=a[i].next){

		v=a[i].to;

		if(dep[v]==dep[u]+1&&(f=dfs(v,t,min(limit,a[i].w)))){

			a[i].w-=f;a[i^1].w+=f;

			flow+=f;limit-=f;

			if(!limit) return flow;

		}

	}

	return flow;

}

int dinic(int s,int t){

	int re=0;

	while(bfs(s,t)) re+=dfs(s,t,inf);

	return re;

}

void init(){memset(first,-1,sizeof(first));memset(a,0,sizeof(a));cnt=-1;}

int e[110][110];

int main(){

	int i,j,tmp1,tmp2;char s[110];

	while(~scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)){

		init();a1++;a2++;b1++;b2++;

		for(i=1;i<=n;i++){

			scanf("%s",s);

			for(j=1;j<=n;j++){

				if(s[j-1]=='X') e[i][j]=0;

				if(s[j-1]=='O') e[i][j]=2;

				if(s[j-1]=='N') e[i][j]=1;

			}

		}

		for(i=1;i<=n;i++){

				for(j=i+1;j<=n;j++){

				if(e[i][j]) add(i,j,((e[i][j]==1)?inf:2));

			}

		}

		add(0,a1,an<<1);add(0,b1,bn<<1);add(a2,n+1,an<<1);add(b2,n+1,bn<<1);

		tmp1=dinic(0,n+1);

		init();

		for(i=1;i<=n;i++){

				for(j=i+1;j<=n;j++){

				if(e[i][j]) add(i,j,((e[i][j]==1)?inf:2));

			}

		}

		add(0,a1,an<<1);add(0,b2,bn<<1);add(a2,n+1,an<<1);add(b1,n+1,bn<<1);

		tmp2=dinic(0,n+1);

		if((tmp1!=(an<<1)+(bn<<1))||(tmp2!=(an<<1)+(bn<<1))) puts("No");

		else puts("Yes");

	}

}

巴特西

[CQOI2014][bzoj3504] 危桥 [最大流]

题面

思路

Code

最新文章

热门文章