Chlience

【题解】LOJ 2115 「HNOI2015」落忆枫音
Problem给定一个有向无环图,编号为 $1$ 的点没有入边,保证至少存在一个树形子图使得 $1$ 号点可以到达...
扫描右侧二维码阅读全文
11
2019/02

【题解】LOJ 2115 「HNOI2015」落忆枫音

Problem

给定一个有向无环图,编号为 $1$ 的点没有入边,保证至少存在一个树形子图使得 $1$ 号点可以到达任意点

问添加一条边 $(x,y)$ 后有多少个树形子图使得 $1$ 号点可以到达任意点

Thought

由于给定的是一个有向无环图,那么在原图中只需要对除根节点外的点选择一条入边,即为一个合法方案,答案为 $\prod deg[i]​$

考虑加入 $(x,y)$ 到合法方案中,有可能生成了某个含有环的情况

显然环上必然包含新加入的那条边,所以相当于减去

$$ \sum_S \prod deg[i](i\not \in S) $$

其中 $S$ 为某条 $(y,x)$ 路径上的点的集合

设 $f[u]=\sum_S \prod deg[i](i\not \in S)$ ,其中 $S$ 为某条 $(y,u)$ 路径上点的集合

那么显然有 $f[y]=\prod deg[i](i\neq y)$
假设有边 $(u,v)​$ ,有转移:

$$ f[v]=f[v]+\frac{f[u]}{deg[v]} $$

由于是在 $DAG$ 上,可以直接拓扑求得 $f$

最终答案我 $\prod deg[i]-f[x]$

注意当 $y=1$ 时特殊判断

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 100010;
const int mod = 1000000007;

struct Edge {
    int t, n;
}e[N << 1];
int head[N], tot;
int deg[N], _deg[N];
int n, m, x, y;
int inv[N], f[N];

queue <int> q;

void calInv() {
    inv[1] = 1;
    for(int i = 2; i <= n; ++ i)
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
}

void addedge(int u, int v) {
    e[++ tot] = {v, head[u]};
    head[u] = tot;
}

void topology() {
    for(int i = 1; i <= n; ++ i)
        if(deg[i] == 0)
            q.push(i);
    while(!q.empty()) {
        int now = q.front(); q.pop();
        f[now] = 1ll * f[now] * inv[_deg[now]] % mod;
        for(int i = head[now]; i; i = e[i].n) {
            f[e[i].t] += f[now];
            if(f[e[i].t] >= mod) f[e[i].t] -= mod;
            if(! -- deg[e[i].t])
                q.push(e[i].t);
        }
    }
}
int main() {
    n = read(); m = read();
    x = read(); y = read();
    calInv();
    ++ _deg[y];
    for(int i = 1; i <= m; ++ i) {
        int u = read(), v = read();
        ++ deg[v]; ++ _deg[v];
        addedge(u, v);
    }
    int ans = 1;
    for(int i = 2; i <= n; ++ i)
        ans = 1ll * ans * _deg[i] % mod;
    if(y == 1) printf("%d\n", ans);
    else {
        f[y] = ans;
        topology();
        printf("%d\n", (ans - f[x] + mod) % mod);
    }
    return 0;
}
Last modification:February 11th, 2019 at 03:39 pm

Leave a Comment