题解：P1543 [POI2004] SZP

fishing_cat · 2024-10-16 20:21:45 · 题解

题意

在一个基环树森林上，选出一些点，要求每一个选出的点都至少有一个没被选出的父节点。问最多可以选多少个。

思路

对于每一个入度为零的点，因为一定是没有点去监督他的，所以一定不选。再基于贪心的思想，这个点不选了，那么他的儿子结点就成了至少有一个没被选出的父节点的状态，所以是一定要选的。

对于上面的操作，可以用类似拓扑排序的方法，再拓扑的过程中，去维护要选的点个数。

做完拓扑排序后，剩下的入度仍不为零的点就是环以及单点了。对于环，还是贪心，隔一个选一个是最优的，所以这些的可选点个数就是环的长度下取整；至于单点，没有可选的。

坑点？

有个地方一开始我写错了，调了好久才改出来，错法较为降智，但还是挂出来，希望大家不要像我一样喵。

    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0 && in[i] > 0) {
            huan_sum ++;
        }
    }
    ans += huan_sum / 2;

这是我在处理环时的代码，可以发现，这只猫猫就只是统计了所有在环上点的总个数，最后将个数除二加入答案。

明显是不对的啊！每一个环的可选点都是这一个环的长度除二，这样的弱智操作，只要有两个奇数环就寄了。

但是大气的洛谷还是给了我一个不错的分数呢。

link

code

#include<bits/stdc++.h>
#define ll long long 
#define il inline

using namespace std;
/*快读省了*/
ll n, a[1001000], ans;
ll to[1001000], cnt, in[1001000], vis[1001000], choose[1001000];

il void toposort() {
    queue<ll> q;
    for (int i = 1; i <= n; i++) 
        if (in[i] == 0) // 
            q.push(i);
    ll go_out = 0, huan_sum = 0;
    while(!q.empty()) {
        ll x = q.front();
        q.pop();
        vis[x] = 1; // 标记不在环中
        if (choose[x] == 1) { // 需要选
            in[to[x]] --;
            if (in[to[x]] == 0) q.push(to[x]); 
        } else {
            if (!choose[to[x]]) { // 防止重复统计
                q.push(to[x]);
                go_out ++;
            }
            choose[to[x]] = 1;
        }
    }
    ans += go_out;
    for (int i = 1; i <= n; i++) {
        huan_sum = 0;
        if (vis[i] == 0 && in[i] > 0) { // 不要像我一样错了
            for (int k = i ; vis[k] == 0; k = to[k]) {
                huan_sum ++;
                vis[k] = 1; 
            }
            ans += huan_sum / 2;
        }
    }
    return ;
}

int main() {
    read(n);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
        to[i] = a[i];
        in[a[i]] ++;
    }
    toposort();
    cout << ans << "\n";
    return 0; // 完结撒花
}