费用流,AC但是疑惑
查看原帖
费用流,AC但是疑惑
364848
Bodhi楼主2023/10/29 07:19

将源点s设置成0,输出就全是0;将源点s设置成2n+1,就AC了,这是为啥?

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

using ll = long long;
const int N = 1010;
vector<int> son[N];
ll cost[N][N], h[N], dis[N];
int pre[N], s, t, match[N];
bool inq[N], flow[N][N], vis[N];
inline void add(int &x, int &y, bool cap, ll c)
{
	son[x].push_back(y);
	flow[x][y] = cap;
	cost[x][y] = c;
}
void spfa()
{
	fill(h, h + t + 1, -1e17);
	queue<int> q;
	q.push(s);
	h[s] = 0;
	inq[s] = true;
	int x;
	while (!q.empty())
	{
		x = q.front();
		q.pop();
		inq[x] = false;
		for (int to : son[x])
		{
			if (flow[x][to] && h[x] + cost[x][to] > h[to])
			{
				h[to] = h[x] + cost[x][to];
				if (!inq[to])
				{
					q.push(to);
					inq[to] = true;
				}
			}
		}
	}
}
bool dijkstra()
{
	fill(dis, dis + t + 1, -1e17);
	fill(vis, vis + t + 1, false);
	dis[s] = 0;
	int i, temp = t, x;
	ll c;
	while (temp--)
	{
		x = 0;
		for (i = 1; i <= t; ++i)
		{
			if (!vis[i] && dis[i] > dis[x])
			{
				x = i;
			}
		}
		vis[x] = true;
		for (int to : son[x])
		{
			c = cost[x][to] + h[x] - h[to];
			if (flow[x][to] && dis[x] + c > dis[to])
			{
				dis[to] = dis[x] + c;
				pre[to] = x;
			}
		}
	}
	return dis[t] != -1e17;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, i, x, y;
	ll hh;
	cin >> n >> m;
	s = n + n + 1, t = n + n + 2; // 就是在这里
	for (i = 1; i <= n; ++i)
	{
		add(s, i, true, 0);
		add(i, s, false, 0);
	}
	for (i = 1; i <= m; ++i)
	{
		cin >> x >> y;
		y += n;
		cin >> hh;
		add(x, y, true, hh);
		add(y, x, false, -hh);
	}
	for (i = n + 1; i <= n + n; ++i)
	{
		add(i, t, true, 0);
		add(t, i, false, 0);
	}
	ll ans = 0;
	spfa();
	while (dijkstra())
	{
		for (i = 1; i <= t; ++i)
		{
			h[i] += dis[i];
		}
		x = t;
		while (x != s)
		{
			flow[pre[x]][x] = false;
			flow[x][pre[x]] = true;
			ans += cost[pre[x]][x];
			x = pre[x];
		}
	}
	cout << ans << '\n';
	for (x = n + 1; x <= n + n; ++x)
	{
		for (int to : son[x])
		{
			if (to != t && flow[x][to])
			{
				match[x - n] = to;
				break;
			}
		}
	}
	for (i = 1; i <= n; ++i)
	{
		cout << match[i] << ' ';
	}
	return 0;
}

2023/10/29 07:19
加载中...