EK40pts求助
查看原帖
EK40pts求助
400205
basachenboming楼主2022/3/15 09:09
#include<bits/stdc++.h>
using namespace std;
struct node
{
	int cap,flow;
	int next,to;
}edge[100001];
int n,m,head[100001];
int pre[100001],vis[100001];
int tot=1;
void add(int x,int y,int dis)
{
	edge[++tot].cap=dis;
	edge[tot].to=y;
	edge[tot].next=head[x];
	head[x]=tot;
}
bool bfs(int s,int t)
{
	memset(vis,0,sizeof(vis));
	memset(pre,0,sizeof(pre));
	queue<int>que;
	vis[s]=1;
	que.push(s);
	while(que.size())
	{
		int x=que.front();
		que.pop();
		for(int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to;
			if(!vis[y]&&edge[i].cap>edge[i].flow)
			{
				vis[y]=1;
				pre[y]=i;
				que.push(y);
				if(y==t)
				{
					return true;
				}
			}
		}
	}
	return false;
}
int ek(int s,int t)
{
	int ans=0;
	while(bfs(s,t))
	{
		int d=1e9,v=t;
		while(v!=s)
		{
			int q=pre[v];
			d=min(d,edge[q].cap-edge[q].flow);
			v=edge[q^1].to;
		}
		ans+=d;
		v=t;
		while(v!=s)
		{
			int q=pre[v];
			edge[q].flow+=d;
			edge[q^1].flow-=d;
			v=edge[q^1].to;
		}
	}
	return ans;
}
int main()
{
	int s,t;
	int a,b,c;
	cin>>a>>b>>c;
	int x,y,k;
    int l=0;
	for(int i=1;i<=a;i++)
	{
		for(int j=1;j<=b;j++)	
		{
		cin>>k;
        l++;
		if(k==1)
		{
		add(0,l,1);
		add(l,0,0);
		add(l,(a*b)+(2*i)-1,1);
		add((a*b)+(2*i)-1,l,0);	
		}
        else 
        {
        add(0,l,0);
		add(l,0,0);
		add(l,(a*b)+(2*i)-1,0);
		add((a*b)+(2*i)-1,l,0);	
        }
		}
	}
	for(int i=1;i<=a;i++)
	{
		add((a*b)+(2*i)-1,2*i+(a*b),1);
		add(2*i+(a*b),2*i+(a*b)-1,0);
	}
    l=0;
	for(int i=1;i<=a;i++)
	{
		for(int j=1;j<=c;j++)
		{
			cin>>k;
            l++;
			if(k==1)
			{
		add((a*b)+(2*i),(a*b)+l+a+a,1);
		add(l+a+a+(a*b),(a*b)+(2*i),0);
		add(l+a+a+(a*b),a+a+(a*b)+(b*c)+1,1);
		add(a+a+(a*b)+(b*c)+1,l+a+a+(a*b),0);
			}
            else
            {
        add((a*b)+(2*i),(a*b)+l+a+a,0);
		add(l+a+a+(a*b),(a*b)+(2*i),0);
		add(l+a+a+(a*b),a+a+(a*b)+(b*c)+1,0);
		add(a+a+(a*b)+(b*c)+1,l+a+a+(a*b),0);
            }
		}		

	}
	cout<<ek(0,a+a+(a*b)+(b*c)+1);
	return 0;
}
2022/3/15 09:09
加载中...