数据好水
  • 板块P1402 酒店之王
  • 楼主hgzxwzfHbomb-47
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/5/5 17:05
  • 上次更新2023/10/28 02:06:49
查看原帖
数据好水
571634
hgzxwzfHbomb-47楼主2022/5/5 17:05
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
#define For(x,y,z) for(int x=y;x<=z;x++)
const int N=1e6+10,M=1e6+10;
int head[N],Next[M],edge[M],node[M],incf[N],pre[N],tot=1,maxflow,n,m;
bool vis[N];
void add(int u,int v,int w)
{
	node[++tot]=v;edge[tot]=w;Next[tot]=head[u];head[u]=tot;
	node[++tot]=u;edge[tot]=0;Next[tot]=head[v];head[v]=tot;
}
bool bfs(int s,int t)
{
	memset(vis,0,sizeof(vis));
	queue<int>q;
	q.push(s);
	vis[s]=1;
	incf[s]=1e9;
	while(q.size())
	{
		int cur=q.front();
		q.pop();
		for(int i=head[cur];i;i=Next[i])
		{
			int nt=node[i],w=edge[i];
			if(vis[nt]||!w) continue;
			q.push(nt);
			pre[nt]=i;
			vis[nt]=1;
			incf[nt]=min(incf[cur],w);
			if(nt==t) return 1;
		}
	}
	return 0;
}
void update(int s,int t)
{
	int x=t;
	while(x!=s)
	{
		int i=pre[x];
		edge[i]-=incf[t];
		edge[i^1]+=incf[t];
		x=node[i^1];
	}
	maxflow+=incf[t];
}
int main()
{
	int n,p,q;
	scanf("%d%d%d",&n,&p,&q);
	int s=0,t=n*2+p+q+1;//这里写成 n 都能过
	For(i,1,n)
	{
		For(j,1,p)
		{
			int op;
			scanf("%d",&op);
			if(op) add(j+n*2,i,1);
		}
	}
	For(i,1,n)
	{
		For(j,1,q)
		{
			int op;
			scanf("%d",&op);
			if(op) add(i+n,j+n*2+p,1);
		}
	}
	For(i,1,p) add(s,i+n*2,1);
	For(i,1,q) add(i+n*2+p,t,1);
	For(i,1,n) add(i,i+n,1);
	while(bfs(s,t)) update(s,t);
	printf("%d",maxflow);
	return 0;
}
2022/5/5 17:05
加载中...