首页 > 其他分享 >[POI2004] SZP

[POI2004] SZP

时间:2023-11-01 14:22:05浏览次数:30  
标签:ch int POI2004 特工 选择 maxn SZP define

[POI2004] SZP

题目描述:

Byteotian 中央情报局(BIA)雇佣了许多特工。他们每个人的工作就是监视另一名特工。Byteasar 国王需要进行一次秘密行动,所以他要挑选尽量多的信得过的特工。但是这项任务是如此的机密以至于所有参加行动的特工都必须至少被另一名没有参加任务的特工所监视(就是说如果某个特工参加了行动,那么原先监视他的那些特工中至少要有一个没有参加进行动)。

给出监视任务的详情,要求计算最多能有多少个特工参与其中。

数据范围:

\(1\leq k,a_k\leq n\leq 10^6\)

思路:

我们先把这个图建出来,然后仔细观察一下这个图,发现是个基环树。然后对于基环树的题目,常规考虑方式就是环和树分开来考虑。

先考虑树的情况。发现一个第一眼看起来不是很正确的贪心:对于一个节点,如果可以选择,则就必须选择。

证明:其实在一开始想到这个贪心的时候,我甚至认为这个玩意是错的。但是实际上,我们仔细想一下,会发现在树上的情况肯定是要这样选的。假设我们并没有选择这个节点 \(u\),则要选择 \(a_u\) 这个节点,发现无论选哪个点,他们的贡献都是一样的。与其等着选后面的点,不如就选择这个点,这样后面还能有更多的可能性选择更多的点,因为他影响的位置提前了。如果不太好理解,其实可以画一个链来模拟一下。

我们对于每个树跑完后,最终就会获得若干环。可以发现,环上的点其实和外面的树之间并没有太多关系,所以钦定环上一个点选择了,然后尽可能多的选择点,其实说白了就是 \(\frac{m}{2}\),\(m\) 为环中节点数量。

点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls i<<1
#define rs i<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=1e6+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n;
int to[maxn],ind[maxn];
int vis[maxn],use[maxn];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>to[i];
        ind[to[i]]++;
    }
    queue<int>Q;
    for(int i=1;i<=n;i++)if(!ind[i])Q.push(i);
    int ans=0;
    while(!Q.empty()){
        int u=Q.front();
        Q.pop();
        vis[u]=1;
        ans+=use[u];
        if(!use[to[u]]&&!use[u]){
            use[to[u]]=1;
            Q.push(to[u]);
        }
        if(!--ind[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 j=i;!vis[j];j=to[j]){
            cnt++;
            vis[j]=1;
        }
        ans+=cnt/2;
    }
    cout<<ans<<endl;
    return 0;
}

标签:ch,int,POI2004,特工,选择,maxn,SZP,define
From: https://www.cnblogs.com/Candycar/p/17801895.html

相关文章

  • [POI2004] Gra
    前言:谁知道我是怎么看教练的bug代码AC而怀疑人生的。已经研究困了。思路:题目传送门博弈论最重要的是,发现模型并进行转模。这题很容易发现,与阶梯模型十分相似。可以考虑每个棋子距离\(M\)还有多少空格转化成当前在第几级阶梯。可是当我们转化后发现,胜利条件有一些不一样......
  • P5911 [POI2004]PRZ
    PRZ——PixelRebelz(?传送门哈哈!思路预处理$T_i$以及$W_i$,为状态为$i$时不分组直接过(管他压不压断桥)的时间和总重量。然后$f_i$就是过桥状态为$i......
  • P5914 [POI2004]MOS 题解
    题目传送门分析这是一道小学经典的数学题,对于这种求最短时间的题目,我们要认真考虑两组人员:首先,跑的快的人应当跑的最多,能者多劳。其次,跑的慢的人应当跑的最少,否则会拉......
  • P5911 [POI2004]PRZ——状压dp
    一样,从\(n\le16\)启发用状压dp思路本质上与UVA11825Hackers'Crackdown异曲同工,不过可以通过预处理处理出一组人的集合时间复杂度最坏为\(O(2^{2n})\),当任何一个集合......