关于无汇源上下界可行流
  • 板块学术版
  • 楼主liheyang123
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/15 16:53
  • 上次更新2024/12/15 20:04:24
查看原帖
关于无汇源上下界可行流
534562
liheyang123楼主2024/12/15 16:53

rt,为何RE,problemrecord

code:

#include <bits/stdc++.h>
using namespace std;

const int N = 210;
const int M = 1e4 + 200 + N, INF = 0x7f7f7f7f;
int n, m, s, t;
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
//链式前向星与建图
struct node {
	int to, next, mival, val;
} a[N];
int pre[N], tot = 1;
void add (int u, int v, int mi, int ma) {
	a[++ tot] = {v, pre[u], mi, ma - mi};
	pre[u] = tot;
	a[++ tot] = {u, pre[v], 0, 0};
	pre[v] = tot;
}
//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
int d[N], now[N], he[N];
int f[N];

bool bfs(){
	memset(d, -1, sizeof(d));
	queue<int>q;
	q.push (s);
	d[s] = 1;
	now[s] = pre[s];
	while (!q.empty()){
		int p = q.front();
		q.pop();
		for (int i = pre[p]; i; i = a[i].next){
			int to = a[i].to;
			if (a[i].val && d[to] == -1){
				d[to] = d[p] + 1;
				now[to] = pre[to];
				if(to == t)return 1;
				q.push (to);
			}
		}
	}
	return 0;
}

int find(int x, int lim){
	if (x == t) return lim;
	int flow = 0;
	for(int i = now[x]; i && flow < lim; i = a[i].next){
		now[x] = i;
		int to = a[i].to;
		if (d[to] == d[x] + 1 && a[i].val){
			int t = find(to, min(a[i].val, lim-flow));
			if (!t) d[to] = -1;
			a[i].val -= t;
			a[i ^ 1].val +=t;
			flow +=t;
		}
	}
	return flow;
}

int dinic(){
	int flow, res=0;
	while (bfs()){
		while (1){
			flow = find (s, INF);
			if (flow == 0) break;
			res += flow;
		}
	}
	return res;
}

int main () {
	cin >> n >> m;
	s = 0, t = n + 1;
	for (int i = 1; i <= m; i ++) {
		int x, y, l, r;
		cin >> x >> y >> l >> r;
		add (x, y, l, r);
		he[x] -= l;
		he[y] += l;
	}
	int cnt = 0;
	for (int  i = 1; i <= n; i++) {
		if (he[i] > 0) add (s, i, 0, he[i]), cnt += he[i];
		else if (he[i] < 0) add (i, t, 0, -he[i]);
	}
	if (dinic() != cnt) puts ("NO");
	else {
		puts ("YES");
		for(int i = 2; i <= m * 2 + 1; i += 2)
			cout<<a[i ^ 1].val + a[i].mival<<'\n';
	}
	return 0;
}

其中now为当前弧优化

2024/12/15 16:53
加载中...