2016 湖南省省赛B题《有向无环图》

题目链接【https://vjudge.net/problem/CSU-1804】

题意： 给出一个有向无环图，然后让你算下面的结果，count（i，j）表示i->j之间的路径条数。

题解： 根据公式，可以把SUMa[i]提出来，然后对于没给我i点求SUMcount(i,j)*bj;

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 1e9 + 7;

const int maxn = 1e5 + 15;

int N, M;

LL A[maxn], B[maxn], dp[maxn];

int  vis[maxn];

struct Edge

{

    int to, next;

    Edge (int to = 0, int next = 0): to(to), next(next) {}

} E[maxn];

int head[maxn], tot;

void initedge()

{

    for(int i = 0; i <= N; i++) head[i] = dp[i] = -1, vis[i] = 0;

    tot = 0;

}

void addedge(int  u, int v)

{

    E[tot] = Edge(v, head[u]);

    head[u] = tot++;

}

LL DFS(int u)

{

    if(dp[u] != -1) return dp[u];

    vis[u] = 1;

    dp[u] = 0;

    for(int k = head[u]; ~k; k = E[k].next)

    {

        int v = E[k].to;

        dp[u] = (dp[u] + (B[v] + DFS(v)) % mod) % mod;

    }

    return dp[u];

}

int main ()

{

    while(~scanf("%d %d", &N, &M))

    {

        for(int i = 1; i <= N; i++)

            scanf("%lld %lld", &A[i], &B[i]);

        initedge();

        for(int i = 1; i <= M; i++)

        {

            int u, v;

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

            addedge(u, v);

        }

        for(int i = 1; i <= N; i++)

            if(!vis[i]) DFS(i);

        LL ans = 0;

        for(int i = 1; i <= N; i++)

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

        printf("%lld\n", ans);

    }

    return 0;

}