abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S5391 【卡常题】

发表于 更新于

Description

给你一个有 $2n$ 个点的二分图，每一个部分有 $n$ 个点。右侧的点每个点向两个左侧的点连边，一条边权为 $a$，一条边权为 $b$。激活一个右侧的点需要至少选择一个与它相连的左侧点，选择一个左侧点需要花费它所连出去的所有边的边权和的代价，问你激活所有右侧点所需的最小代价。

Solution

这题本来是真卡常题，但是因为太过于卡常了，于是时限放宽为 1s，成为了假卡常题。

考虑如果一个右侧点向两个左侧点 $i$ 和 $j$ 连边了，那么我们就新建一个图，连一条从 $i$ 到 $j$ 的边，表示 $i$ 和 $j$ 中至少要选一个。

然后我们就得到了一棵基环树。

考虑断掉任意一条环边，那么新图就变成了一棵树，我们设其两端为 $u$ 和 $v$。

于是我们考虑树形 DP 一下。考虑设 $f_{i, 0 / 1}$ 表示当前已经确定了以 $i$ 为根的子树内的点选不选，且点 $i$ 不选 / 选。

我们再前面断掉了一条连接了点 $u$ 和点 $v$ 的边，为了保证其正确性，我们做两遍 DP，一遍以 $u$ 为根，一边以 $v$ 为根，分别取 $f_{u, 1}$ 和 $f_{v, 1}$，然后答案就是它们的 $\min$ 了，即我们强制选择 $u$ 或 $v$。

Code

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
85
86
87
#include <cstdio>
#include <cstring>
#define maxN 1000010
struct Edge{ int x, y, g; bool u; } b[maxN << 1];
int len = 1, X = 0, Y = 0;
int f[maxN][2];
int val[maxN], vis[maxN], h[maxN];
int min (int x, int y)
{
	return x < y ? x : y;
}
void ins (int x, int y)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].g = h[x];
	h[x] = len;
}
void dfs (int x, int from)
{
	if(X)
	{
		return ;
	}
	vis[x] = true;
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(y != from)
		{
			if(vis[y])
			{
				b[i].u = b[i ^ 1].u = true;
				X = x, Y = y;
				return ;
			}
			dfs(y, x);
		}
	}
}
void work (int x, int from)
{
	bool flag = false;
	f[x][0] = f[x][1] = 0;
	for(int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(y != from && !b[i].u)
		{
			flag = true;
			work(y, x);
			f[x][0] += f[y][1];
			f[x][1] += min(f[y][0], f[y][1]);
		}
	}
	if(!flag)
	{
		f[x][0] = 0, f[x][1] = val[x];
	}
	else
	{
		f[x][1] += val[x];
	}
}
int main ()
{
	int n = 0, A = 0, B = 0;
	scanf("%d %d %d", &n, &A, &B);
	for(int i = 1;i <= n; i++)
	{
		int x = 0, y = 0;
		scanf("%d %d", &x, &y);
		val[x] += A, val[y] += B;
		ins(x, y), ins(y, x);
	}
	dfs(1, 0);
	int Ans = 2147483647;
	memset(f, 127 / 3, sizeof(f));
	work(X, 0);
	Ans = min(Ans, f[X][1]);
	memset(f, 127 / 3, sizeof(f));
	work(Y, 0);
	Ans = min(Ans, f[Y][1]);
	printf("%d", Ans);
	return 0;
}