妹子刚学 Dinic写法WA#5求调
查看原帖
妹子刚学 Dinic写法WA#5求调
556545
_anll_楼主2024/12/26 11:03

rt,拍好久拍不出来,应输出 230 输出 231,求大佬帮帮 T T。

#include<queue>
#include<cstring>
#include<iostream>
#define int long long
using namespace std;
const int N=10005,M=5e5+5,inf=1e11;
struct Edge{
	int l,w,nxt;
}edges[M<<1];
int n1,n2,m,s,t,tt=1,head[N],cur[N],vu[N];
void add_edge(int f,int l,int w){
	edges[++tt]={l,w,head[f]};
	head[f]=tt;
}
bool bfs(){
	memset(vu,0,sizeof(vu));
	queue<int> qo;
	qo.push(s),vu[s]=1;
	while(!qo.empty()){
		int x=qo.front();qo.pop();
		if(x==t) return 1;
		for(int i=head[x];i;i=edges[i].nxt){
			int l=edges[i].l,w=edges[i].w;
			if(vu[l]||!w) continue;
			vu[l]=vu[x]+1;qo.push(l);
		}
	}
	return 0;
}
int dfs(int x,int mf,int an=0){
	if(x==t) return mf;
	for(int i=cur[x];i;i=edges[i].nxt){
		cur[x]=i;
		int l=edges[i].l,w=edges[i].w;
		if(vu[l]!=vu[x]+1||!w) continue;
		int f=min(mf,w);f=dfs(l,f);
		mf-=f,an+=f;
		edges[i].w-=f,edges[i^1].w+=f;
		if(!mf) break;
	}
	if(!an) vu[x]=0;
	return an;
}
int Dinic(int ans=0){
	while(bfs()){
		memcpy(cur,head,sizeof(head));
		ans+=dfs(s,inf);
	}
	return ans;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n1>>n2>>m;int f,l;
	s=n1+n2+1,t=n1+n2+2;
	for(int i=1;i<=m;i++){
		cin>>f>>l;l=n1+l;
		add_edge(f,l,1);add_edge(l,f,0);
		add_edge(l,f,1);add_edge(f,l,0);
	}
	for(int i=1;i<=n1;i++){
		add_edge(s,i,1);
		add_edge(i,s,0);
	}
	for(int i=1;i<=n2;i++){
		add_edge(i+n1,t,1);
		add_edge(t,i+n1,0);
	}
	cout<<Dinic();
	return 0;
}
2024/12/26 11:03
加载中...