xml地图|网站地图|网站标签 [设为首页] [加入收藏]

bzoj3037--贪心,bzoj3037

来源:http://www.ccidsi.com 作者:最新解决方案 人气:170 发布时间:2019-11-13
摘要:bzoj3037--贪心,bzoj3037 主题素材概略: applepi手里有一本书《创世纪》,里面著录了那样叁个传说…… 苍天手中持有N种被称作“世界成分”的事物,今后她要把它们中的大器晚成都部队

bzoj3037--贪心,bzoj3037

主题素材概略:

applepi手里有一本书《创世纪》,里面著录了那样叁个传说……
苍天手中持有N 种被称作“世界成分”的事物,今后她要把它们中的大器晚成都部队分排放到多个新的空中中去以建筑世界。各个世界成分都得以界定其余风度翩翩种世界成分,所以说上天希望具有被投放的社会风气成分都有最少多少个尚无被排泄的世界成分能够范围它,那样天公就足以保证对世界的主宰。
鉴于特别闻明的有关于上天能或不可能营造一块连自身都不能够举起的大石头的二律背反命题,大家明白上天不是德才兼备的,何况不独有不是文武双全的,他竟是有业务供给找你扶植——上天希望知道他最多可以投放多少种世界成分,然则她只会O(2^N) 级其他算法。就算真主具有非常多的年华,不过她也是个急天性。你须要帮忙天公解除这些主题素材。

思路:

其实这题能够转正为最小支配集。但有风姿罗曼蒂克种更加快的贪婪算法。

假造全体入度为0的点。显明那一个点都不得不不选。对于各种那么些点能决定的点,就算它前面并未有被调控,那么选它一定是最优的(自个儿画个图就理解了卡塔 尔(阿拉伯语:قطر‎。

进而先更新全数入度为0的点,由于各种点唯有一条出边,剩下的点一定能结成多少个简单环。而对于每一个有n个点的简短环,最四只能选n/2个点。求出全体环就能够总结出答案了。

切实看代码:

图片 1

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int Ans,i,j,k,n,Num,Cnt,m,a[1000001],d[1000001],c[1000001],l=1,r;
bool v[1000001];
int main()
{
    scanf("%d",&n);
    for(i=1;i<=n;i  )scanf("%d",&a[i]),d[a[i]]  ;
    for(i=1;i<=n;i  )
    if(!d[i])c[  r]=i;
    while(l<=r)
    {
        if(!v[c[l]]&&!v[a[c[l]]]){
            Ans  ;v[a[c[l]]]=1;
            if(--d[a[a[c[l]]]]==0)c[  r]=a[a[c[l]]];
        }
        v[c[l  ]]=1;
    }
    for(i=1;i<=n;i  )
    if(!v[i]){
        Cnt=0;
        j=i;
        while(a[j]!=i){
            v[j]=1;
            Cnt  ;
            j=a[j];
        }
        v[j]=1;
        Ans =(Cnt 1)>>1;
    }
    printf("%d",Ans);
    return 0;
}

bzoj3037

 

标题大体: applepi手里有一本书《创世纪》,里面著录了那样贰个轶事…… 上天手中具有N 种被称作“世界成分”的东...

本文由68399皇家赌场发布于最新解决方案,转载请注明出处:bzoj3037--贪心,bzoj3037

关键词: 68399皇家赌场

上一篇:游戏编程系列

下一篇:没有了

最火资讯