M_sea

洛谷3472 [POI2008]MAF-Mafia
LuoguBZOJ分析显然原图是一颗基环内向树。第一问显然,如果一个点入度为$0$,那么它一定不会死。于是跑拓扑排...
扫描右侧二维码阅读全文
31
2019/01

洛谷3472 [POI2008]MAF-Mafia

Luogu

BZOJ

分析

显然原图是一颗基环内向树。

第一问

显然,如果一个点入度为$0$,那么它一定不会死。

于是跑拓扑排序。最后会剩下很多环。

然后每个环最多存活$sz/2$个人。

然后最小死亡人数就是总人数减去最大存活人数。

第二问

显然,如果一个点入度不为$0$,那么它一定可以被打死。

然后每个环最少存活一人。

细节和具体实现见代码吧...真的讲不清楚qwq

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n;
int a[N],deg[N];

namespace SubTask1 {
    queue<int> Q;
    int vis[N],deg[N];
    inline void work() {
        memcpy(deg,::deg,sizeof(deg));
        int ans=0;
        for (re int i=1;i<=n;++i)
            if (!deg[i]) ++ans,Q.push(i);
        while (!Q.empty()) {
            int u=a[Q.front()],v=a[u]; Q.pop();
            if (vis[u]) continue;
            vis[u]=1,--deg[v];
            if (!deg[v]&&!vis[v]) ++ans,Q.push(v);
        }
        for (re int i=1;i<=n;++i) {
            if (deg[i]&&!vis[i]) {
                int now=i,sz=0;
                while (!vis[now]) vis[now]=1,now=a[now],++sz;
                ans+=sz>>1;
            }
        }
        printf("%d ",n-ans);
    }
}

namespace SubTask2 {
    int vis[N];
    inline void work() {
        int ans=0;
        for (re int i=1;i<=n;++i) {
            if (deg[i]) continue; 
            ++ans; int now=i;
            while (!vis[now]) vis[now]=1,now=a[now];
        }
        for (re int i=1;i<=n;++i) {
            if (vis[i]||a[i]==i) continue;
            ++ans; int now=i;
            while (!vis[now]) vis[now]=1,now=a[now];
        }
        printf("%d\n",n-ans);
    }
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read(),++deg[a[i]];
    SubTask1::work(); SubTask2::work();
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 12 PM

发表评论