湖南省第十二届大学生计算机程序设计竞赛 B 有向无环图 拓扑DP

时间：2022-06-25 08:38:11

1804: 有向无环图

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 187  Solved: 80
[Submit][Status][Web Board]

Description

Bobo 有一个 n 个点，m 条边的有向无环图（即对于任意点 v，不存在从点 v 开始、点 v 结束的路径）。
为了方便，点用 1,2,…,n 编号。 设 count(x,y) 表示点 x 到点 y 不同的路径数量（规定 count(x,x)=0），Bobo 想知道
湖南省第十二届大学生计算机程序设计竞赛 B 有向无环图 拓扑DP
除以 (109+7) 的余数。
其中，ai,bj 是给定的数列。

Input

输入包含不超过 15 组数据。
每组数据的第一行包含两个整数 n,m (1≤n,m≤105).
接下来 n 行的第 i 行包含两个整数 ai,bi (0≤ai,bi≤109).
最后 m 行的第 i 行包含两个整数 ui,vi，代表一条从点 ui 到 vi 的边 (1≤ui,vi≤n)。

Output

对于每组数据，输出一个整数表示要求的值。

Sample Input

3 3

1 1

1 1

1 1

1 2

1 3

2 3

2 2

1 0

0 2

1 2

1 2

2 1

500000000 0

0 500000000

1 2

Sample Output

4

4

250000014

题解：

　　quality：dp[u]表示从u出发能到达的所有v的count[v]*b[v]之和，那么u的一个后继v对dp[u]有dp[v]+b[v]的贡献，按照反向拓扑序dp

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18;

const double Pi = acos(-1.0);

const int N = 2e5+, M = 1e6+, mod = 1e9+, inf = ;

int n,m;

LL a[N],b[N];

int d[N],t,head[N];

LL dp[N];

struct ss{int to,next;}e[N * ];

void add(int u,int v) {e[t].to=v;e[t].next = head[u];head[u]=t++;}

int main() {

        while(scanf("%d%d",&n,&m)!=EOF) {

            for(int i = ; i <= n; ++i)  scanf("%I64d%I64d",&a[i],&b[i]);

            memset(d,,sizeof(d));t = ;

            memset(head,,sizeof(head));

            for(int i = ; i <= m; ++i) {

                int u,v;

                scanf("%d%d",&u,&v);

                add(v,u);

                d[u] += ;

            }

            memset(dp,,sizeof(dp));

            queue<int  > q;

            for(int i = ; i <= n; ++i) {

                if(d[i] == ) {

                    q.push(i);

                }

            }

            while(!q.empty()) {

                int u = q.front();

                q.pop();

                for(int i = head[u]; i; i = e[i].next) {

                    int to = e[i].to;

                    dp[to] += (dp[u] + b[u]);

                    dp[to] %= mod;

                    d[to]--;

                    if(d[to] == ) q.push(to);

                }

            }

            LL ans = ;

            for(int i = ; i <= n; ++i) {

              //  cout<<dp[i]<<endl;

                ans += ((a[i] * dp[i])%mod);

                ans %= mod;

            }

            cout<<(ans+mod)% mod<<endl;

        }

    return ;

}

相关文章