题解：P11812 [PA 2015] 精确打击 / Kontrmanifestacja

kind_Ygg · 2026-10-22 17:30:28 · 题解

这个题真的好诡异啊。

谨此纪念我的第二篇黑题题解。

题目大意

题目的大概意思，没什么好解释的。

思路

考虑先把 NIE 判掉，也就是原图是个 DAG。

其次，考虑 k=0 的情况，也就是这些环的交是空集，考虑如何快速判断这种情况。首先我们找到一个主环（下文将主环称作 M），那么这些环交集一定会出现在 M 上面，考虑一个环删掉任意一个点就不会是环了。因此我们将 M 上的点全部删掉（并不是真的删掉再重建图，染个色就行了），跑一遍剩下的图，如果还出现的环，那么就说明出现的那个环和 M 没有交，因此直接输出 0 即可；或者，可以直接跑拓扑排序，若最后有非主环上的点度数不为 0，也是同理（但是可能这里会有一部分 k=0 的情况没有判掉，没关系，继续往下看）。

我们继续对于 M 进行考虑，不难发现，如果从 M 上的一个点 S 能通过非主环边（即删掉 M 原图剩下的那个 DAG 上的边），到达 M 的另一个点 T，那么会将一段区间打上不能作为最后的交点的 tag，代码实现就是做差分，进行分讨（下文的 ok 数组代表重新将 M 上的点按顺时针编号，len 代表 M 的大小）。

若 ok_S<ok_T，就将 [ok_S+1,ok_T-1] 打上标记；若 ok_S\ge ok_T，就将 [ok_S+1,len]\cup[1,ok_T-1] 打上标记，可以自己画图理解。特殊地，我们将 ok_S=ok_T 归类到第二种是由于 M 上除了 S 这个点其他都不合法。

考虑如何处理这个东西，首先不跨环尾是好处理的，考虑用记忆化搜索处理每个点 S 经过非 M 上的边能到达的最大编号 mx_S，时间复杂度显然是线性的，然后考虑用差分数组给 [ok_S+1,mx_S-1] 打上标记，代表这段区间不合法，但是你发现跨过环尾久不好处理了。举个例子，假设 len=5，ok_S=3，但是能到达的最远的点是 2，但是考虑这个肯定是不会被记录到 to_S 里面去的，因为 S 可能可以到 4。我们不妨有记录最小值，但是发现编号为 2 的点比编号为 1 的点离 S 的距离更远，也不能很好地处理答案，我们真正要找的，是不大于 ok_S 的编号最大的点，这个是不能直接从 S 维护的，但是，考虑到我们维护能到的编号最小的点 mn_S，若满足 mn_S\le ok_S 则一定会将 [ok_S+1,len] 打上标记；反之，若 mn_S>ok_S，连能到达的编号最小的点都不会跨过环尾，那么就不会打上标记了，mn_S 在此处有这个作用。

但是我们还是没有解决如何处理跨过环尾后面一段标记的问题，既然正着不好找，不妨直接从终点 T 出发，沿反图找到编号最大的点的 S，然后若 ok_S\ge ok_T，就将 [1,ok_T-1] 打上标记。考虑这样做为什么是对的，是因为只要存在的 S 能经过环尾到 T，就会产生这样的贡献，而贪心找最大的 S 无疑是最优的，这样这道黑就被我们做完啦，最后记得还原差分数组。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500010;
int n,m,state[N],fa[N],ok[N],vis[N],prex[N],mx[N],mn[N],gd[N];
vector<int> G[N],g[N],cir;
bool dfs(int u)
{
    state[u]=1;
    for(int v:G[u])
    {
        if(!state[v])
        {
            fa[v]=u;
            if(dfs(v)) return 1;
        }
        else if(state[v]==1)
        {
            int x=u;
            while(x!=v)
            {
                cir.push_back(x);
                x=fa[x];
            }
            cir.push_back(v);
            reverse(cir.begin(),cir.end());
            return 1;
        }
    }
    state[u]=2;
    return 0;
}
bool check(int u)
{
    state[u]=1;
    for(int v:G[u])
    {
        if(ok[v]) continue;
        if(state[v]==1) return 1;
        if(!state[v] and check(v)) return 1;
    }
    state[u]=2;
    return 0;
}
void del(int l,int r)
{
    l=max(1LL,l);
    r=min((int)cir.size(),r);
    if(l>r) return;
    prex[l]++;
    prex[r+1]--;
}
void solve1(int u)
{
    if(vis[u]) return;
    vis[u]=1;
    if(ok[u])
    {
        mx[u]=mn[u]=ok[u];
        return;
    }
    mx[u]=0;
    mn[u]=n+1;
    for(int v:G[u])
    {
        solve1(v);
        mx[u]=max(mx[u],mx[v]);
        mn[u]=min(mn[u],mn[v]);
    }
}
void solve2(int u)
{
    if(vis[u]) return;
    vis[u]=1;
    if(ok[u])
    {
        mx[u]=ok[u];
        return;
    }
    mx[u]=0;
    for(int v:g[u])
    {
        solve2(v);
        mx[u]=max(mx[u],mx[v]);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);//正图
        g[v].push_back(u);//反图
    }
    for(int i=1;i<=n;i++)
        if(!state[i] and dfs(i)) break;
    if(cir.empty())
    {
        cout<<"NIE\n";
        return 0;
    }//判 DAG
    int tot=0;
    for(auto v:cir)
        ok[v]=++tot;
    memset(state,0,sizeof(state));
    for(int i=1;i<=n;i++)
        if(!ok[i] and !state[i] and check(i))
        {
            cout<<0<<"\n";//判断又没有其他环（这里也可以写拓扑然后判断是否还有点有度数）
            return 0;
        }
    memset(vis,0,sizeof(vis));
    for(int idx:cir)
    {
        for(int to:G[idx])
        {
            solve1(to);
            if(mx[to] and mx[to]>=ok[idx])
                del(ok[idx]+1,mx[to]-1);
            if(mn[to]!=n+1 and mn[to]<=ok[idx])
                del(ok[idx]+1,cir.size());
        }
    }
    memset(vis,0,sizeof(vis));
    for(int idx:cir)
    {
        for(int to:g[idx])
        {
            solve2(to);
            if(mx[to] and mx[to]>=ok[idx])
                del(1,ok[idx]-1);
        }
    }
    int k=cir.size(),ans=0;
    for(int i=1;i<=k;i++)
    {
        prex[i]+=prex[i-1];
        if(!prex[i]) gd[cir[i-1]]=1;
    }
    for(int i=1;i<=n;i++)
        ans+=gd[i];
    cout<<ans<<"\n";
    for(int i=1;i<=n;i++)
        if(gd[i]) cout<<i<<" ";
    return 0;
}