CF949C Data Center Maintenance

这题如果没有搞清楚题意，其实结论是并不“显然”的

题目其实是让你主动推迟有且仅有一个点，并将所有会因此受影响的点也都连锁着推迟下去，问最少会有几个点推迟

注意这个”主动推迟“，这意味着即使已经满足条件了你还是得要推迟一个点

搞懂了题意，接下来的思路就好理解了

我们发现“推迟”是一种单向关系，即，如果我使你不得不推迟，而你却不会使我不得不推迟

将这种单向关系转成图论的单向边

边的是否添加，即询问两者的是否满足

发现一个点只要有出度那它肯定不是最优的

如A->B，选A必带B，选B可无A

所以首先可以确定答案节点没有出度的

其次，由于强联通分量里的点都是可以互相到达的，所以只要其一推迟，另外的都得推迟

于是缩点，经保留size

问题变成在DAG上找一个没有出度的最小的点

$O(n)$扫一遍即可

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int N=1e5+5;
int h[N],en,H,n,m,scc[N],dfn[N],low[N],st[N],lim,cnt,du[N],sn,ans,sz[N],a[N];
bool v[N];

struct edge{
    int n,u,v;
}e[N];

void add(int x,int y){
    e[++en]=(edge){h[x],x,y};
    h[x]=en;
}

void tarjan(int x){ //找强联通分量
    low[x]=dfn[x]=++cnt;
    v[x]=1;
    st[++lim]=x;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(!dfn[y]){
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else{
            if(v[y]) low[x]=min(low[x],dfn[y]);
        }
    }
    if(low[x]==dfn[x]){
        int top;
        sn++;
        for(;;){
            top=st[lim--];
            scc[top]=sn;
            v[top]=0;
            sz[sn]++;
            if(top==x) return ;
        }
    }
}

signed main(){
    read(n);read(m);read(H);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1,x,y;i<=m;i++){
        read(x);read(y);
        if((a[x]+1)%H==a[y]) add(x,y); //边的添加（关系的判断）
        if((a[y]+1)%H==a[x]) add(y,x);
    }
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=en;i++){
        int x=scc[e[i].u],y=scc[e[i].v]; //根据原先加的边判定出度
        if(x^y) du[x]++;
    }
    sz[0]=0x3f3f3f3f;
    for(int i=1;i<=sn;i++) if(!du[i]){
        if(sz[i]<sz[ans]) ans=i; //取无出度节点的最小size
    }
    write(sz[ans]);puts("");
    for(int i=1;i<=n;i++) if(scc[i]==ans) //是这个强联通分量的就输出
        write(i),putchar(' ');
}
赏

fighter