isap求调
查看原帖
isap求调
1032755
hello_sqt楼主2023/11/3 14:32

跑得还没ek快,是不是哪里写假了

#include <iostream>
#include <queue>
#include <cstring>
#define maxn 50005
#define inf 0x7f7f7f7f
using namespace std;

int n,n1,n2,n3,m1,m2,u,v,s,t,ans;
int cnt=1,head[maxn],dis[maxn],gap[maxn];
struct edge{
	int v,w,nxt;
}e[1000000];

void add(int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

void bfs(){
	queue<int> q;q.push(t);
	memset(dis,-1,sizeof dis);
	dis[t]=0;gap[0]=1;
	while (q.size()){
		int tmp=q.front();q.pop();
		for (int i=head[tmp];i;i=e[i].nxt){
			if (e[i^1].w&&dis[e[i].v]==-1){
				dis[e[i].v]=dis[tmp]+1;
				gap[dis[e[i].v]]++;
				q.push(e[i].v);
			}
		}
	}
}

int dfs(int now,int flow){
	if (now==t) return flow;
	int used=0;
	for (int i=head[now];i;i=e[i].nxt){
		if (e[i].w&&dis[e[i].v]+1==dis[now]){
			int f=dfs(e[i].v,min(flow-used,e[i].w));
			used+=f;
			e[i].w-=f;
			e[i^1].w+=f;
			if (used==flow) return flow;
		}
	}
	if (!(--gap[dis[now]])) dis[now]=n1*2+n2+n3+1;
	dis[now]++;
	gap[dis[now]]++;
	return used;
}

int main(){
//	freopen("P1231_2.in","r",stdin);
	ios::sync_with_stdio(false);
	cin>>n1>>n2>>n3>>m1;
	s=0;t=n1*2+n2+n3+1;
	for (int i=1;i<=m1;i++){
		cin>>u>>v; u+=n2;
		add(v,u,1);add(u,v,0);
	}
	for (int i=n2+1;i<=n1+n2;i++){
		add(i,i+n1,1);add(i+n1,i,0);
	}
	cin>>m2;
	for (int i=1;i<=m2;i++){
		cin>>u>>v;u+=(n2+n1);v+=(n1*2+n2);
		add(u,v,1);add(v,u,0);
	}
	for (int i=1;i<=n2;i++){
		add(s,i,1);add(i,s,0);
	}
	for (int i=n2+n1*2+1;i<=t-1;i++){
		add(i,t,1);add(t,i,0);
	}
	bfs();
	while (dis[s]<n1*2+n2+n3+1){
		ans+=dfs(s,inf);
	}
	cout<<ans;
}
2023/11/3 14:32
加载中...