由题可以知道，每一条边都是有向边。一个检查站只能保护一个环上的路口，即检查站的个数也是环的个数。
题目的第一问求最小花费，也就是就每个环上建一个检查站的最小花费之和。因此用 tarjan 求出每一个强联通分量以及该分量内的最小花费，最后求一个和。
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
| void tarjan (int u)
{
low[u] = dfn[u] = ++times;
s.push (u);
for (int i = head[u];i;i = nxt[i])
{
int v = to[i];
if (!dfn[v])
{
tarjan (v);
low[u] = min (low[u],low[v]);
}
else if (!scc[v])
low[u] = min (low[u],dfn[v]);
}
if (low[u] == dfn[u])
{
++scc_cnt;
while (true)
{
int x = s.top ();
s.pop ();
scc[x] = scc_cnt;
mn[scc_cnt] = min (mn[scc_cnt],cost[x]);
if (x == u) break;
}
}
}
|
最后相加时注意最小花费是不用取模的，所以答案为 $\sum^{n}_{i = 1} mn[i]$。
再来看第二问，求方案数。由于肯定要做到每一个强连通分量中选的检查站花费一定最优，所以只要求每一个分量中花费为 $mn[i]$ 的个数，然后根据乘法原理将它乘起来即可。注意这是需要取模的，答案为 $\prod^{n}_{i = 1} num[i]$。
1
2
3
4
| for (int i = 1;i <= n;++i)
if (cost[i] == mn[scc[i]]) ++num[scc[i]];
for (int i = 1;i <= scc_cnt;++i)
ans_cnt = (ll)ans_cnt * num[i] % MOD;
|
