网络流 EK 70分WA #8910
查看原帖
网络流 EK 70分WA #8910
590571
_weishiqi66_楼主2024/1/5 17:23

试过ek模板了应该不是模板部分有问题。网络流建模方面的思路是:建立一个源点,连接所有左边的点,建议一个汇点,将所有右边的点与其连接。

刚学网络流,而且特别菜,麻烦各位大佬指正错误。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
const int inf=0x3f3f3f3f;
int a,b,k,ans,s,t;
struct EDGE{
	int to,next,w;
}e[N];
int head[N],cnt=1;
void add(int x,int y,int z){
	++cnt;
	e[cnt].to=y;
	e[cnt].w=z;
	e[cnt].next=head[x];
	head[x]=cnt;
}
int pre[N],v[N],incf[N];
bool bfs(){
	memset(v,0,sizeof(v));
	queue<int> q;
	q.push(s);
	v[s]=1;
	incf[s]=inf;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=e[i].next){
			if(e[i].w!=0){
				int y=e[i].to;
				if(v[y]) continue;
				incf[y]=min(incf[x],e[i].w);
				pre[y]=i;
				q.push(y),v[y]=1;
				if(y==t) return 1;
			} 
		}
	}
	return 0;
	
}
void update(){
	int x=t;
	while(x!=s){
		int i=pre[x];
		e[i].w-=incf[t];
		e[i^1].w+=incf[t];
		x=e[i^1].to;
	}
	ans+=incf[t];
}
int main(){
	scanf("%d%d%d",&a,&b,&k);
	s=0,t=a+b+1;
	for(int i=1;i<=a;i++){
		add(s,i,1),add(i,s,0);
	}
	for(int i=a+1;i<=a+b;i++){
		add(i,t,1),add(t,i,0);
	}
	for(int i=1;i<=k;i++){
		int x,y;  
		scanf("%d%d",&x,&y);
		y+=a;
		add(x,y,1);
		add(y,x,0);
	} 
	while(bfs()){
		update();
	}
	printf("%d",ans);
	return 0;
}
2024/1/5 17:23
加载中...