P3436 [POI2006] PRO-Professor Szu

Jerrywang09 · 2024-12-20 15:10:50 · 题解

给一个思路非常顺、没啥细节的实现。

首先，如果能绕进一个环内，然后从这环能够到达终点，则方案数为无穷。因为教授每天都可以在这个环内绕不同的圈数！

找环，就是求强连通。然后缩点，建出反图。因为我们要从终点出发 DP，DP 出每个环是否可以到达终点。

然后，再次 DP，求出每个强连通到终点的方案数。对于那些可以到终点的环，方案数设为 36501，并保证所有 >36500 的都设成 36501。

自环也需要当做环处理。

// P3436 [POI2006] PRO-Professor Szu
#include <cstdio>
#include <iostream>
#define ll long long
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
const int N=1000010, M=N+N;
using namespace std;
char buf[1<<23], *p1=buf, *p2=buf;
#define gc() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int x=0, f=1; char c=gc();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=gc();
    while('0'<=c && c<='9') x=(x<<3)+(x<<1)+c-'0', c=gc();
    return x*f;
}

int n, m, t;
struct edge {int u, v, n;} e[M]; int tot, h1[N], h2[N];
void add(int hd[], int u, int v)
{
    e[++tot]={u, v, hd[u]}, hd[u]=tot;
}
int dfn[N], low[N], stk[N], sz[N], c[N], tim, top, scc; bool in[N], self[N], loop[N];
void tarjan(int u)
{
    low[u]=dfn[u]=++tim; stk[++top]=u, in[u]=1;
    for(int i=h1[u]; i; i=e[i].n)
    {
        int v=e[i].v;
        if(!dfn[v])
            tarjan(v), low[u]=min(low[u], low[v]);
        else if(in[v])
            low[u]=min(low[u], dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        int v=0; scc++;
        while(v!=u)
        {
            v=stk[top--], in[v]=0;
            sz[scc]++, c[v]=scc;
        }
        if(sz[scc]>1 || self[v]) loop[scc]=1;
    }
}
int deg[N], q[N], res[N], hh, tt, cnt; bool vis[N];
void topo()
{
    hh=1, tt=0;
    rep(i, 1, scc) if(!deg[i]) q[++tt]=i;
    while(hh<=tt)
    {
        int u=q[hh++];
        for(int i=h2[u]; i; i=e[i].n)
        {
            int v=e[i].v;
            if(!--deg[v]) q[++tt]=v;
        }
    }
}

int main()
{
#ifdef Jerrywang
    freopen("../in.txt", "r", stdin);
#endif
    n=read(), m=read(), t=n+1;
    rep(i, 1, m)
    {
        int u=read(), v=read(); add(h1, u, v);
        if(u==v) self[u]=1;
    }
    rep(i, 1, t) if(!dfn[i]) tarjan(i);
    rep(i, 1, m)
    {
        int u=e[i].u, v=e[i].v;
        u=c[u], v=c[v];
        if(u!=v) add(h2, v, u), deg[u]++;
    }
    topo();
    vis[c[t]]=1;
    rep(kk, 1, scc)
    {
        int u=q[kk];
        for(int i=h2[u]; i; i=e[i].n)
        {
            int v=e[i].v;
            vis[v]|=vis[u];
        }
    }
    res[c[t]]=1;
    rep(i, 1, scc) if(vis[i] && loop[i]) res[i]=36501;
    rep(kk, 1, scc)
    {
        int u=q[kk];
        for(int i=h2[u]; i; i=e[i].n)
        {
            int v=e[i].v;
            res[v]+=res[u];
            if(res[v]>36500) res[v]=36501;
        }
    }
    int mx=0;
    rep(i, 1, n) mx=max(mx, res[c[i]]);
    if(mx>36500) puts("zawsze"); else printf("%d\n", mx);
    rep(i, 1, n) if(res[c[i]]==mx) cnt++;
    printf("%d\n", cnt);
    rep(i, 1, n) if(res[c[i]]==mx) printf("%d ", i);

    return 0;
}