BZOJ3876 支线剧情

发表于

  题意:一个DAG，每条路径的起点固定为1，每条边带权，用几条路径，以最少权值代价使整个DAG每条边都至少被覆盖一次。

  每条边至少被覆盖一次，这可以设计成下界为1，上界INF的上下界网络流。但是边带权，而且权最少，要跑费用流?
  上下界最小费用可行流!将汇点向源点连边之后原图变成一个无源汇的图。从超级源向超级汇跑一个最小费用最大流即可。因为保证有解，不用担心其他问题。
  话说写费用流总是不记得更新p数组(用来记录pre)啊。要注意。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define erep(i, u) for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
#define ms(a, b) memset(a, b, sizeof a);
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c - '0'; isdigit(c = getchar()); (x *= 10) += c - '0');
    if(flag) x = -x; return x;
}
const int maxn = 310, maxm = 16000, INF = 0x3f3f3f3f;
int n;
int head[maxn], to[maxm << 1], nxt[maxm << 1], c[maxm << 1], w[maxm << 1], e = 1;
void ae(int x, int y, int C, int W) { to[++e] = y; nxt[e] = head[x]; head[x] = e; c[e] = C; w[e] = W; }
namespace MCMF
{
	int S, T, dis[maxn], res[maxn], p[maxn], cost;
	bool inq[maxn];
	bool SPFA()
	{
		ms(dis, INF);
		queue<int> q; ms(inq, 0);
		q.push(S); dis[S] = p[S] = 0; res[S] = INF;
		while(!q.empty())
		{
			int u = q.front(); q.pop(); inq[u] = 0;
			erep(i, u) if(c[i] && chkmin(dis[v], dis[u] + w[i]))
			{
				res[v] = min(res[u], c[i]); p[v] = i;
				if(!inq[v]) q.push(v), inq[v] = 1;
			}
		}
		if(dis[T] == INF) return 0;
		cost += res[T] * dis[T];
		for(int u = T; u != S; u = to[p[u] ^ 1]) c[p[u]] -= res[T], c[p[u] ^ 1] += res[T];
		return 1;
	}
	int maxflow(int s, int t)
	{
		S = s, T = t; cost = 0;
		while(SPFA());
		return cost;
	}
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
	read(n); int s = 0, t = n + 1, ss = n + 2, tt = n + 3;
	ae(s, 1, INF, 0), ae(1, s, 0, 0);
	rep(i, 1, n) ae(i, t, INF, 0), ae(t, i, 0, 0);
	ae(t, s, INF, 0); ae(s, t, 0, 0);
	rep(i, 1, n)
	{
		int k, v, W; read(k);
		rep(j, 1, k)
		{
			read(v), read(W);
			ae(ss, v, 1, W); ae(v, ss, 0, -W);
			ae(i, v, INF, W); ae(v, i, 0, -W);
			ae(i, tt, 1, 0); ae(tt, i, 0, 0);
		}
	}
	printf("%d\n", MCMF::maxflow(ss, tt));
	return 0;
}