求助啊啊啊,怎么做QAQ,本地就过不去
查看原帖
求助啊啊啊,怎么做QAQ,本地就过不去
222220
elinatotoro楼主2022/5/6 23:12
#include<bits/stdc++.h>
using namespace std;
struct node
{
	long long next,to,ww;
};
node e[3200001];
long long s,t;
long long deep[100001],head[200001],sum=1,mapp[51][51]; 
long long inf=1e8;
void add(int x,int y,int z)
{
	sum++;
	e[sum].to=y;
	e[sum].next=head[x];
	e[sum].ww=z;
	head[x]=sum;
}
bool bfs()
{
	long long i,u,v;
	queue<long long>qu;
	memset(deep,0,sizeof(deep));
	deep[s]=1;
	qu.push(s);
	while(!qu.empty())
	{
		u=qu.front();
		qu.pop();
		for(i=head[u];i;i=e[i].next)
		{
			v=e[i].to;
			if(e[i].ww>0&&!deep[v])
			{
				deep[v]=deep[u]+1;
				qu.push(v);
			}
		}
	}
	return deep[t];
}
long long dfs(long long u,long long flow)
{
	if(u==t)
	{
		return flow;
	}
	long long fl=0,i,v,c;
	for(i=head[u];i&&flow;i=e[i].next)
	{
		v=e[i].to;
		if(e[i].ww>0&&deep[v]==deep[u]+1)
		{
			c=dfs(v,min(flow,e[i].ww));
			e[i].ww-=c;
			e[i^1].ww+=c;
			flow-=c;
			fl+=c;
		}
	}
	if(fl==0)
	{
		deep[u]=0;
	}
	return fl;
}
long long dinic()
{
	long long maxflow=0;
	while(bfs())
	{
		maxflow+=dfs(s,inf);
	}
	return maxflow;
}
int main()
{
	long long n,a1,a2,an,b1,b2,bn,i,j,xx;
	char x;
    while(~scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&a1,&a2,&an,&b1,&b2,&bn)) 
	{
		xx=an+bn;
		memset(head,0,sizeof(head));
		a1++;
		a2++;
		b1++;
		b2++;
	    s=0;
		t=n*n+1;
		sum=1;
		add(s,a1,an);
	    add(a1,s,0);
		add(a2,t,an);
		add(t,a2,0);
	    add(s,b1,bn);
	    add(b1,s,0);
		add(b2,t,bn);
		add(t,b2,0);
	    for(i=1;i<=n;i++)
	    {
	    	for(j=1;j<=n;j++)
	    	{
	    		cin>>x;
	    		if(x=='O')
	    		{
	    			mapp[i][j]=1;
				}
			}
		}
	    for(i=1;i<=n;i++)
		{
	        for(j=i+1;j<=n;j++)
			{
	            if(mapp[i][j]==1) 
				{
					add(i,j,2);
					add(j,i,0);
				}
	            if(mapp[i][j]==0) 
				{
					add(i,j,inf);
					add(j,i,0);
				}
	        }
	    }
	    if(dinic()!=xx)
		{
	        cout<<"No"<<endl;
	    	continue;
	    }
	    memset(head,0,sizeof(head));
	    sum=1;
	    add(s,a1,an);
	    add(a1,s,0);
		add(a2,t,an);
		add(t,a2,0);
	    add(s,b2,bn);
	    add(b2,s,0);
		add(b1,t,bn);
		add(t,b1,0);
	    for(i=1;i<=n;i++)
		{
	        for(j=i+1;j<=n;j++)
			{
	            if(mapp[i][j]==1) 
				{
					add(i,j,2);
					add(j,i,0);
				}
	            if(mapp[i][j]==0) 
				{
					add(i,j,inf);	
					add(j,i,0);
				}
	        }
	    }
	    if(dinic()!=xx)
		{
			cout<<"No"<<endl;
		}
	    else
	    {
	    	cout<<"Yes"<<endl;
		}
	}
    return 0;
}
2022/5/6 23:12
加载中...