P3436 [POI2006]PRO-Professor Szu

Coros_Trusds · 2022-07-05 23:05:02 · 题解

更好的阅读体验

题目大意

某大学校内有一栋主楼，还有 n 栋住宅楼。这些楼之间由一些单向道路连接，但是任意两栋楼之间可能有多条道路，也可能存在起点和终点为同一栋楼的环路。已知任意一栋住宅楼都存在至少一条前往主楼的路线。

现在有一位古怪的教授，他希望每天去主楼上班的路线不同。

一条上班路线中，每栋楼都可以访问任意多次。我们称两条上班路线是不同的，当且仅当两条路线中存在一条路是不同的（两栋楼之间的多条道路被视为是不同的道路）。

现在教授希望知道，从哪些住宅楼前往主楼的上班路线数最多。

题目分析

为了方便，不妨反着建图，这样题目就转化为从主楼前往哪些住宅楼的上班路线数最多，多点转换为了单点，可以 \verb!tarjan! 缩点后直接套路上拓扑排序即可。

这道题思路不难，重要的是如下的几项难点：

• 可能存在 (u,v),u=v 的数据（即自环），此时我们把它也当成连通块大小大于 1 的连通块。

• 拓扑排序时，若当前节点可以被访问到，那么下一个节点也能被访问到，如果下一个节点能被访问到，则有 dp_v\gets dp_v+dp_u，dp 表示方案数。

• 特殊地，因为所有路径和点可以无限次经过，所以一个连通块内所有点都有无数种方案数，而之前我们提到此处视自环的大小大于 1 且属于连通块，所以解决了自环的问题。如果方案数超过了 36500，则强制改为 36500。

代码

#include <bits/stdc++.h>
#define enter putchar(10)
#define debug(c,que) std::cerr << #c << " = " << c << que
#define cek(c) puts(c)
#define blow(arr,st,ed,w) for(register int i = (st);i <= (ed); ++ i) std::cout << arr[i] << w;
#define speed_up() std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
#define mst(a,k) memset(a,k,sizeof(a))
#define stop return(0)
const int mod = 1e9 + 7;
inline int MOD(int x) {
    if(x < 0) x += mod;
    return x % mod;
}
namespace Newstd {
    char buf[1 << 21],*p1 = buf,*p2 = buf;
    inline int getc() {
        return p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++;
    }
#ifndef ONLINE_JUDGE
#define getc getchar
#endif
    inline int read() {
        int ret = 0,f = 0;char ch = getc();
        while (!isdigit(ch)) {
            if(ch == '-') f = 1;
            ch = getc();
        }
        while (isdigit(ch)) {
            ret = (ret << 3) + (ret << 1) + ch - 48;
            ch = getc();
        }
        return f ? -ret : ret;
    }
    inline double double_read() {
        long long ret = 0,w = 1,aft = 0,dot = 0,num = 0;
        char ch = getc();
        while (!isdigit(ch)) {
            if (ch == '-') w = -1;
            ch = getc();
        }
        while (isdigit(ch) || ch == '.') {
            if (ch == '.') {
                dot = 1;
            } else if (dot == 0) {
                ret = (ret << 3) + (ret << 1) + ch - 48;
            } else {
                aft = (aft << 3) + (aft << 1) + ch - '0';
                num ++;
            }
            ch = getc();
        }
        return (pow(0.1,num) * aft + ret) * w;
    }
    inline void write(int x) {
        if(x < 0) {
            putchar('-');
            x = -x;
        }
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace Newstd;

const int N = 1e6 + 5;
struct Graph {
    struct Node {
        int u,v,nxt;
    } gra[N];
    int head[N];
    int idx;
    inline void add(int u,int v) {
        gra[++ idx] = (Node){u,v,head[u]},head[u] = idx;
    }
} g1,g2;
int in[N],id[N],dfn[N],low[N],dp[N],g[N],siz[N];
bool in_stack[N],vis[N];
std::stack <int> st;
int n,m,dfntim,cnt;

inline void tarjan(int now) {
    dfn[now] = low[now] = ++ dfntim,in_stack[now] = true;
    st.push(now);
    for (register int i = g1.head[now];i;i = g1.gra[i].nxt) {
        int v = g1.gra[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[now] = std::min(low[now],low[v]);
        } else if (in_stack[v]) {
            low[now] = std::min(low[now],dfn[v]);
        }
    }
    if (dfn[now] == low[now]) {
        cnt ++;
        int u;
        do {
            u = st.top();st.pop();
            in_stack[u] = false,id[u] = cnt,siz[cnt] ++;
        } while (u != now);
    }
}
inline void topo() {
    std::queue <int> q;
    for (register int i = 1;i <= cnt; ++ i) {
        if (!in[i]) q.push(i);
    }
    vis[id[n]] = true,dp[id[n]] = 1;
    while (!q.empty()) {
        int u = q.front();q.pop();
        for (register int i = g2.head[u];i;i = g2.gra[i].nxt) {
            int v = g2.gra[i].v;
            in[v] --;
            if (!in[v]) q.push(v);
            if (vis[u]) vis[v] = true;
            dp[v] += dp[u];
            if (siz[v] > 1 && vis[v]) dp[v] = 36500;
            if (dp[v] > 36500) dp[v] = 36500;
        }
    }
}
int main(void) {
    n = read() + 1,m = read();
    for (register int i = 1;i <= m; ++ i) {
        int u = read(),v = read();
        g1.add(v,u);
    }
    for (register int i = 1;i <= n; ++ i) {
        if (!dfn[i]) tarjan(i);
    }
    for (register int i = 1;i <= g1.idx; ++ i) {
        if (g1.gra[i].u == g1.gra[i].v) siz[id[g1.gra[i].u]] ++;
    }
    for (register int i = 1;i <= n; ++ i) {
        for (register int j = g1.head[i];j;j = g1.gra[j].nxt) {
            int v = g1.gra[j].v;
            if (id[i] != id[v]) {
                g2.add(id[i],id[v]);
                in[id[v]] ++;
            }
        }
    }
    topo();
    int ans = 0,num = 0;
    for (register int i = 1;i <= n; ++ i) {
        if (vis[id[i]]) {
            g[i] = dp[id[i]];
            ans = std::max(ans,g[i]);
        }
    }
    for (register int i = 1;i <= n; ++ i) {
        if (vis[id[i]] && g[i] == ans) num ++;
    }
    if (ans == 36500) {
        puts("zawsze");
    } else {
        printf("%d\n",ans);
    }
    printf("%d\n",num);
    for (register int i = 1;i <= n; ++ i) {
        if (vis[id[i]] && g[i] == ans) {
            printf("%d ",i);
        }
    }

    return 0;
}