Bzoj1877 SDOI 2009 晨跑 费用流

真的是很水的费用流

只需要把每个点拆成两个点

然后中间的费用是0，流量是1

这步的作用大家都懂对吧，目的是为了防止经过一个点两次

然后如果路口ab之间有路

只需要把a的出点和b的入点连边，费用不变，容量是1

然后问题就解决了

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 100009
#define inf 0x7fffffff/3
#define rep(i, j, k) for(int i = j; i <= k; i++)

using namespace std;

int to[2 * MAX], head[MAX], from[MAX * 2], flow[MAX * 2];
int cost[2 * MAX], next[2 * MAX], n, m, tot = 1, p[MAX], a[MAX];
int dis[MAX], in[MAX], ans = 0;

inline void add (int x, int y, int Flow, int Cost)
{
	to[++tot] = y;
	from[tot] = x;
	next[tot] = head[x];
	head[x] = tot;
	flow[tot] = Flow;
	cost[tot] = Cost;

	to[++tot] = x;
	from[tot] = y;
	next[tot] = head[y];
	head[y] = tot;
	flow[tot] = 0;
	cost[tot] = -Cost;
}

bool spfa (int s, int t, int &Flow, int &Cost)
{
	rep (i, 1, n * 2 + 2)
		dis[i] = inf;
	memset (in, 0, sizeof(in));
	queue <int> q;
	
	dis[s] = 0;
	in[s] = 1;
	q.push (s);
	p[s] = 0;
	a[s] = inf;

	while (!q.empty ())
	{
		int now = q.front();
		q.pop();
		in[now] = 0;

		for (int i = head[now]; i; i = next[i])
		{
			if (flow[i] > 0 && dis[to[i]] > dis[now] + cost[i])
			{
				//printf ("fuck %d\n", to[i]);
				//system ("pause");
				dis[to[i]] = dis[now] + cost[i];
				p[to[i]] = i;
				a[to[i]] = min (a[now], flow[i]);
				if (!in[to[i]])
					q.push (to[i]), in[to[i]] = 1;
			}
		}
	}
	if (dis[t] == inf )
		return 0;
	Flow += a[t];
	ans += a[t];
	Cost += dis[t] * a[t];
	int pos = t;
	while (pos != s)
	{
		flow[p[pos]] -= a[t];
		flow[p[pos] ^ 1] += a[t];
		pos = from[p[pos]];
	}
	return 1;
}

inline void solve()
{
	int Flow = 0, Cost = 0;
	while (spfa (1, n, Flow, Cost));
	printf ("%d ", ans);
	printf ("%d\n", Cost);
}

int main()
{
	scanf ("%d%d", &n, &m);
	rep (i, 1, m)
	{
		int a1, a2, a3;
		scanf ("%d%d%d", &a1, &a2, &a3);
		add (a1 + n, a2, 1, a3);
	}
	rep (i, 1, n)
		if (i == 1 || i == n)
			add (i, i + n, inf , 0);
		else
			add (i, i + n, 1, 0);

	solve ();

	return 0;
}