Dinic求助
查看原帖
Dinic求助
250640
stueam楼主2023/8/31 22:10

RT,不知道哪里出问题了

#include <bits/stdc++.h>
using namespace std;
const int V = 1100;
const int E = 10010;
template<class T>
struct FlowGraph {
	int s,t,vtot;
	int h[V],idx;
	int dis[V],cur[V];
	struct edge {
		int v,nxt;
		T f;
	}e[E * 2];
	void add(int a,int b,T f) {
		e[idx] = {b,h[a],f}; h[a] = idx++;
		e[idx] = {a,h[b],f}; h[b] = idx++;
	}
	bool bfs() {
		queue <int> q;
		for(int i = 1;i <= vtot;i++) {
			dis[i] = 0;
			cur[i] = h[i];
		}
		q.push(s); dis[s] = 1;
		while(!q.empty()) {
			int u = q.front(); q.pop();
			for(int i = h[u];~i;i = e[i].nxt) {
				if(e[i].f && !dis[e[i].v]) {
					int v = e[i].v;
					dis[v] = dis[u] + 1;
					if(v == t)	return true;
					q.push(v);
				}
			}
		}
		return false;
	}
	T dfs(int u,T m) {
		if(u == t)	return m;
		int flow = 0;
		for(int i = cur[u];~i;cur[u] = i = e[i].nxt)
			if(e[i].f && dis[e[i].v] == dis[u] + 1) {
				T f = dfs(e[i].v,min(m,e[i].f));
				e[i].f -= f;
				e[i ^ 1].f += f;
				m -= f;
				flow += f;
				if(!m)	break;
			}
		if(!flow)	dis[u] = -1;
		return flow;
	}
	T dinic() {
		T flow = 0,r;
		while(bfs()) while(r = dfs(s,1e9)) flow += r;
		return flow;
	}
	void init(int s_,int t_,int vtot_) {
		s = s_;
		t = t_;
		vtot = vtot_;
		idx = 0;
		memset(h,-1,sizeof h);
	}
};
FlowGraph <int> g;
int n,m,s,t;
int main() {
	cin >> m >> n;
	s = n + 1,t = n + 2;
	g.init(s,t,t);
	int a,b;
	for(int i = 1;i <= m;i++)
		g.add(s,i,1);
	for(int i = m + 1;i <= n;i++)
		g.add(i,t,1);
	while(cin >> a >> b,a != -1) 
		g.add(a,b,1);
	cout << g.dinic() << endl;
	for(int i = 0; i < g.idx; i += 2)
        if (g.e[i].v > m && g.e[i].v <= n && !g.e[i].f)
            printf("%d %d\n", g.e[i ^ 1].v, g.e[i].v);
}
```cpp
2023/8/31 22:10
加载中...