P4015 运输问题

	while (spfa(s, t)) dinic(s, t, INF); 
	printf("%d", ans);
	for (int i = 2; i <= tot; i += 2) edge[i].dis += edge[i ^ 1].dis, edge[i ^ 1].dis = 0, swap(edge[i].dis, edge[i ^ 1].dis);
	ans = 0;
	while (spfa(t, s)) dinic(t, s, INF);
	printf("\n%d", -ans);

这样子先跑最小费用最大流， 再跑最大费用最大流就没有错。

while (spfa(s, t)) dinic(s, t, INF); printf("%d", ans);
	for (int i = 2; i <= tot; i += 2) edge[i].dis += edge[i ^ 1].dis, edge[i ^ 1].dis = 0, edge[i].val *= -1, edge[i ^ 1].val *= -1;
	ans = 0;
	while (spfa(s, t)) dinic(s, t, INF);
	printf("\n%d", -ans);

这个样子就会错一个点， 求问这两个代码有区别吗。 AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
const int M = 1e5 + 10;
const int INF = 1e9;
int n, m, s, t, head[N], tot = 1, ans, res, a[N], b[N];
struct Edge{ int to, next, dis, val; }edge[M << 1];
void add(int x, int y, int z, int c) { 
	edge[++tot] = {y, head[x], z, c}; head[x] = tot; 
	edge[++tot] = {x, head[y], 0, -c}; head[y] = tot;
}
int d[N], ins[N], now[N];
deque<int> q;
bool spfa(int s, int t) {
	memset(d, 0x3f, sizeof d);
	q.push_back(s); now[s] = head[s];
	ins[s] = 1, d[s] = 0;
	while (!q.empty()) {
//		if (q.size() > 1 && d[q.front()] > d[q.back()]) swap(q.front(), q.back()); 
		int u = q.front(); q.pop_front(); ins[u] = 0;
		for (int i = head[u]; i; i = edge[i].next) {
			int v = edge[i].to;
			if (edge[i].dis && d[v] > d[u] + edge[i].val) {
				d[v] = d[u] + edge[i].val;
				now[v] = head[v];
				if (!ins[v]) {
//					if (d[v] < d[q.front()] && q.size()) q.push_front(v);
//					else q.push_back(v);
					q.push_back(v);
					ins[v] = 1; 
				}
			}
		}
	}
	return d[t] != 0x3f3f3f3f;
}
int vis[N];
int dinic(int u, int t, int flow) {
	if (u == t) return flow;
	int rest = flow;
	vis[u] = 1;
	for (int i = now[u]; i; i = edge[i].next) {
		now[u] = i;
		int v = edge[i].to;
		if (!vis[v] && edge[i].dis && d[v] == d[u] + edge[i].val) {
			int k = dinic(v, t, min(edge[i].dis, rest));
			if (!k) d[v] = 0;
			edge[i].dis -= k;
			edge[i ^ 1].dis += k;
			ans += edge[i].val * k;
			rest -= k;
		}
	} 
	vis[u] = 0;
	return flow - rest;
}
int main() {
//	freopen("P4015_7.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	scanf("%d%d", &m, &n); s = m + n + 1, t = m + n + 2;
	for (int i = 1, x; i <= m; i++) scanf("%d", &x), add(s, i + n, x, 0);
	for (int i = 1, x; i <= n; i++) scanf("%d", &x), add(i, t, x, 0);
	for (int i = 1; i <= m; i++) {
		for (int j = 1, x; j <= n; j++) {
			scanf("%d", &x);
			add(i + n, j, INF, x); 
		}
	}
	while (spfa(s, t)) dinic(s, t, INF); 
	printf("%d", ans);
	for (int i = 2; i <= tot; i += 2) edge[i].dis += edge[i ^ 1].dis, edge[i ^ 1].dis = 0, swap(edge[i].dis, edge[i ^ 1].dis);
	ans = 0;
	while (spfa(t, s)) dinic(t, s, INF);
	printf("\n%d", -ans);
	return 0;
}