萌新刚学网络流求助
查看原帖
萌新刚学网络流求助
574568
Dr_Gilbert南科蛤蟆楼主2022/5/26 21:40

RT\text{RT},自己写的 Dinic\text{Dinic},交主题库模板题过了,但交这个却没过 ,不知道是不是我写的 Dinic\text{Dinic} 有问题。求大佬帮助

码风有点奇怪(

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
const int M=2.5e5+10;
const int INF=0x7fffffff;
struct edge{
	int v,val,ops;
}e[M<<2];
int dis[N],st[N],n,m,s,t,tot;
vector<vector<int>> G;
bool bfs(){
	memset(dis,0,sizeof(dis));
	queue<int> que;que.push(s);
	dis[s]=1;
	while (que.size()){
		int x=que.front();
		que.pop();
		for (int id:G[x]){
			auto p=e[id];
			int v=p.v,w=p.val;
			if (w&&!dis[v]){
				st[x]=0;
				dis[v]=dis[x]+1;
				que.push(v); 
			}
		}
	}
	return dis[t];
}
int dinic(int x, int in){
	if (x==t) return in;
	int out=0;
	for (int i=st[x];i<G[x].size();i++){
		int id=G[x][i];auto p=e[id];
		st[x]=i;
		int v=p.v,w=p.val,ops=p.ops;
		if (dis[x]+1==dis[v]&&w>0){
			int tmp=dinic(v,min(w,in));
			in-=tmp;out+=tmp;
			e[id].val-=tmp;e[ops].val+=tmp;
		}
	}
	if (!out) dis[x]=0;
	return out;
}
void add(int u,int v,int w){
	e[tot+1]={v,w,tot+2};
	e[tot+2]={u,0,tot+1};
	G[u].push_back(tot+1);
	G[v].push_back(tot+2);
	tot+=2;return;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);cout.tie(nullptr); 
	int e;cin>>n>>m>>e;
	G.resize(n+m+10);s=0,t=n+m+1;
	for (int i=1;i<=e;i++){
		int u,v;cin>>u>>v;
		add(u,v+n,1);
	}
	for (int i=1;i<=n;i++) add(s,i,1);
	for (int i=1;i<=m;i++) add(n+i,t,1); 
	int maxflow=0;
	while (bfs()){
		maxflow+=dinic(s,INF);
//		cout<<maxflow<<endl;
	}
	cout<<maxflow;
	return 0;
}
2022/5/26 21:40
加载中...