30pts求调
查看原帖
30pts求调
838514
Six_chestnuts楼主2025/2/6 19:27
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e4+5,M=2e5+5,INF=1e9;
int n1,n2,n3,m1,m2,s,t,tot,maxflow,to[M],nxt[M],w[M],head[M],pre[N],inc[N];
bool vis[N];
void add(int x,int y,int z)
{
	to[++tot]=y;
	w[tot]=z;
	nxt[tot]=head[x];
	head[x]=tot;
	
	to[++tot]=x;
	w[tot]=0;
	nxt[tot]=head[y];
	head[y]=tot;
}
bool bfs()
{
	queue<int> q;
	memset(vis,0,sizeof(vis));
	q.push(s);
	vis[s]=1;
	inc[s]=INF;
	while(q.empty()==false)
	{
		int x=q.front();
		q.pop();
		for(int i=head[x];i;i=nxt[i])
		{
			int y=to[i],val=w[i];
			if(!vis[y]&&val)
			{
				vis[y]=1;
				inc[y]=min(inc[x],val);
				pre[y]=i;
				q.push(y);
				if(y==t)
					return 1;
			}
		}
	}
	return  0;
}
void update()
{
	int cur=t;
	maxflow+=inc[t];
	while(cur!=s)
	{
		int last=pre[cur];
		w[last]-=inc[t];
		w[last^1]+=inc[t];
		cur=to[last^1];
	}
	return ;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n1>>n2>>n3;
	tot=1,t=n1*2+n2+n3+1;
	memset(head,0,sizeof(head));
	cin>>m1;
	for(int i=1,x,y;i<=m1;i++)
	{
		cin>>x>>y;
		add(x+n1+n2+n3,y+n1,1);
	}
	cin>>m2;
	for(int i=1,x,y;i<=m2;i++)
	{
		cin>>x>>y;
		add(y+n1+n2,x,1);
	}
	for(int i=n1+n2+1;i<=n1+n2+n3;i++)
		add(s,i,1);
	for(int i=n1+1;i<=n1+n2;i++)
		add(i,t,1);
	for(int i=1;i<=n1;i++)
		add(i,i+n1+n2+n3,1);
	while(bfs())
		update();
	cout<<maxflow; 
	return 0;
 }

除了第1、3和4个点,其他的都T了,数组开小点就会RE

2025/2/6 19:27
加载中...