POI2004 SZP

· · 题解

原题链接

题意是如果我们选择了一个点 x，至少存在一个点 y 没被选择且 a_y=x。

我们贪心的想到，如果一个点 x 可以被选择，那么我们一定要选择 x 这个点。证明：因为如果我们没有选择 x 这个点，也就只是使得 a_x 可以被选择，而选择 a_x 和选择 x 的贡献是一样的，所以我们贪心的使得选择 x 就是正确的。

另外每个点出度为 1，所以图是一个基环内向树。而基环内向树的性质是：从每个点开始，沿着唯一出边走都会走到环上。

那么入度为 0 的点我们一定是不能选择的，所以我们从所有入度为 0 的点开始搜索，按照上述规则选择点，直到走到一个环上，把环放到最后考虑。

那么剩下的问题就是若干个环，一些点可以直接被选择（受环外点影响），问最多可以选择多少个点。随便找一个位置破环成链，讨论这个位置选或不选，取最大值即可。具体看代码

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
}
const int MAXN=1e6+10,INF=1e9+7;
int n,a[MAXN],into[MAXN],ans;
bool vis[MAXN],b[MAXN],f[MAXN];
queue <int> q;
int dfs(int x,int pre)
{
    vis[x]=true;int ans=0;
    //f[x] 表示是否选择 x ,b[x]表示 x 是否可以通过环外点选择上
    if(a[x]!=pre)//下一个点不是开始的点
    {
        if(!f[x]||b[a[x]]) f[a[x]]=1,ans+=1;//可以选择就加 1
        ans+=dfs(a[x],pre);
    }
    else if(!(!f[x]||b[pre])&&f[pre]) ans-=1;
    //如果下一个点是开始的点，并且一开始默认选择了但并不能选择的话，让当前点 x 不再被选择，所以减掉 1
    f[x]=false;//回溯时候把 f[x] 重新设为 false
    return ans;
}
int main()
{
    n=read();
    for(register int i=1;i<=n;++i) a[i]=read(),into[a[i]]++;//记录入度数
    for(register int i=1;i<=n;++i) if(!into[i]) q.push(i);//入度为 0 的放入队列
    while(!q.empty())
    {
        int x=q.front();q.pop();
        vis[x]=true;if(b[x]) ans++;//如果被选择了，答案 +1
        if(!b[x]) b[a[x]]=true;//当前点没被选，下一个点可以被选，一定选
        if(!--into[a[x]]) q.push(a[x]);//如果入度为 0 了放入队列，这样剩下的就一定是环上的点
    }
    for(register int i=1;i<=n;++i)
    {
        if(!vis[i])//找到一个点断开环
        {
            f[i]=true;//f[i] 表示是否选择 i
            int ans1=dfs(i,i)+1;//加上第一个点的 1
            int ans2=dfs(i,i);
            ans+=max(ans1,ans2);//取最优情况
        }
    }
    printf("%d\n",ans);
    return 0;
}