题目链接
https://www.lydsy.com/JudgeOnline/problem.php?id=1124
https://www.luogu.org/problemnew/show/P3472
分析
首先, 每个神枪手都只有一个目标.
若是把每个神枪手当成一个点来建图, 那么这个图每个点的出度都是1(基环内向树)
既然\(N \leq 10^6\), 这道题基本上是个贪心.
分别考虑最少存活人数和最大存活人数的求解. (死亡人数 = N - 存活人数)
1. 最少存活人数(minlive)
若是一个点入度为0, 那么这个点必定存活.
对于基环内向森林中的每一个基环内向树, 判断其中是否有入度为0的点.
若有, 那么这个基环内向树中除了入度为0的点其他点都可以被杀(环上的点先开枪使环上只留1个点, 再按照拓扑序逆序开枪即可)
此时minlive += cnt[ ind==0 ]
若无, 那么其中必定1个点可以存活, minlive++(环长为1的需要特判).
2. 最多存活人数(maxlive)
这个问题相对复杂.
先考虑内向树上maxlive的求解.
内向树上叶子节点必定存活. 而且, 从下到上, 每一层的节点个数都\(\ge\) 其上一层节点个数.所以取从下到上的1, 3, 5, 7....层是最优方案.
如: 这棵内向树有3层.
所以, 将入度为0的点(最下层点集)取出, 用类似于拓扑排序分层的方法, 隔一层向队列中加点即可(详见代码).
具体来说, 如果a杀死了b, 那么b指向的人c就少了一个可以杀死他的人. 所以把c的入度-1. 当c入度为0时, c必定存活, 那么可以把c加入队列, 作为a这一层之后的"活人"层(这一点与拓扑排序相同)
再考虑基环内向树上maxlive的求解.
用以上算法求解过后, 图中必定剩下若干个环.
这些环对maxlive的贡献是 环长/2.
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, k) for(register int i=(j);i<=(k);++i)
#define per(i, j, k) for(register int i=(j);i>=(k);--i)
int read(){
int ret = 0, f = 1; char c=getchar();
while(isdigit(c) == false) {
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)) ret = ret*10+c-'0', c=getchar();
return ret*f;
}
const int maxn= 1e6+5;
int n;
int to[maxn], ind[maxn];
int L, R, q[maxn];
int maxlive, minlive;
bool dead[maxn], vis[maxn];
void getdead(){
minlive = 0;
L = R = 1; //[L, R)
rep(i, 1, n){
if(ind[i] == 0){
minlive++;
q[R++] = i; //将入度为0的点加入队列
for(int cur = i; !vis[cur]; vis[cur] = 1, cur = to[cur]);
}
}
rep(i, 1, n) if(!vis[i]){
int looplen = 0;
for(int cur = i; !vis[cur]; vis[cur] = 1, cur = to[cur])looplen++;
if(looplen != 1) {
minlive += 1;
}
} //calculate minlive
memset(vis, 0, sizeof vis);
while(R - L > 0){
int cur = q[L++], u = to[cur];
if(vis[cur]) continue;
maxlive++, vis[cur] = 1;//cur 存活
if(vis[u] == 0){ //给to[u]除去一个威胁
vis[u] = 1, ind[to[u]]--;
if(ind[to[u]] == 0) q[R++] = to[u];
}
assert(u <= n);
}
// printf("bfs : %d %d\n" ,maxlive, minlive);
rep(i, 1, n) if(!vis[i]) {
int looplen = 0, cur;
for(cur = i; !vis[cur]; vis[cur] = 1, cur = to[cur])looplen++;
if(cur == i) maxlive += (looplen)/2;
else maxlive += (looplen+1)/2;
} //calculate maxlive
// printf("clearloop : %d %d\n" ,maxlive, minlive);
}
signed main(){
// freopen("5.in", "r", stdin);
n =read();
rep(i, 1, n) {
to[i] = read();
ind[to[i]]++;
}
getdead();
printf("%d %d\n", n - maxlive, n - minlive);
return 0;
}