P1543 [POI2004] SZP 题解

Fishing_Boat · 2023-09-02 16:23:40 · 题解

首先，这道题有一个贪心就是能选就选，因为如果一个点能选但却没有选，那就只能选择它的子节点，这样一定不会更优。然后就只剩下一堆环，而这些环都是不受其它点影响的，所以可以先钦定一个点不选，然后贪心，实际上就是将环的大小除以 2，下取整即可。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define ll long long
#define cmax(a,b) a=max(a,b)
#define cmin(a,b) a=min(a,b)
#define rst(a,x) memset(a,x,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define FAST ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

using namespace std;

const int N(1e6+5);

int n,to[N],in[N],vis[N],ans;
bool use[N];
queue <int> Q;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>to[i];
        in[to[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        int u=Q.front();Q.pop();vis[u]=1;
        ans+=use[u];
        if(!use[u]&&!use[to[u]]){
            use[to[u]]=1;
            Q.push(to[u]); 
        } 
        in[to[u]]--;
        if(!in[to[u]]&&!use[to[u]]) Q.push(to[u]);
    }
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        int cnt=0;
        for(int u=i;!vis[u];u=to[u]){
            cnt++,vis[u]=1;
        }
        ans+=cnt/2;
    }
    cout<<ans;
    return 0;
}