代码64pts求调
查看原帖
代码64pts求调
643818
I_AK_CTS楼主2025/6/19 08:25
#include<bits/stdc++.h>
using namespace std;
const int N=25005,INF=0x3f3f3f3f;
struct E
{
	int ne,to,c;
}e[N];
int h[N],cur[N],n,p,q,ct,lv[N];
void add(int u,int v)
{
	e[ct]={h[u],v,1},h[u]=ct++;
	e[ct]={h[v],u,0},h[v]=ct++; 
}
bool bfs()
{
	memcpy(cur,h,sizeof(h));
	memset(lv,-1,sizeof(lv));
	queue<int> qq;
	qq.push(0),lv[0]=0;
	while(!qq.empty())
	{
		int x=qq.front();qq.pop();
		for(int i=h[x];~i;i=e[i].ne)
		{
			int v=e[i].to,w=e[i].c;
			if(w&&lv[v]==-1)
			{
				lv[v]=lv[x]+1;
				qq.push(v);
			}
		}
	}
	return ~lv[n+p+q+1];
}
int dfs(int x,int F)
{
	if(x==n+p+q+1||!F) return F;
	int res=0;
	for(int i=cur[x];~i&&F;i=e[i].ne)
	{
		int v=e[i].to,w=e[i].c;
		cur[x]=i;
		if(lv[v]==lv[x]+1&&w)
		{
			int c=dfs(v,min(w,F));
			res+=c,F-=c,e[i].c-=c,e[i^1].c+=c;
		}
	}
	return res;
}
int dinic()
{
	int res=0;
	while(bfs()) res+=dfs(0,INF);
	return res;
}
int main()
{
	memset(h,-1,sizeof(h));
	cin>>n>>p>>q;//汇点:n+p+q+1
	for(int i=1;i<=p;i++)
		add(0,i);
	for(int i=n+p+1;i<=n+p+q;i++)
		add(i,n+p+q+1);
	for(int i=1;i<=n;i++)
		for(int j=1,x;j<=p;j++)
		{
			cin>>x;
			if(x) add(j,i+p);
		}
	for(int i=1;i<=n;i++)
		for(int j=1,x;j<=q;j++)
		{
			cin>>x;
			if(x) add(i+p,j+n+p);
		}
	cout<<dinic();
	return 0;
}

大致思路是分5层,分别是源点,pp 个房间,nn 个人,qq 道菜,汇点,每条边边权都是 11

2025/6/19 08:25
加载中...