CSU 1804: 有向无环图 (拓扑排序)

爱被打了一巴掌 2022-07-14 12:11 188阅读 0赞

题目链接：[点击打开链接][Link 1]

## 1804: 有向无环图 ##

Time Limit: 5 Sec Memory Limit: 128 MB  
Submit: 421 Solved: 186  
\[[Submit][]\]\[[Status][]\]\[[Web Board][]\]

## Description ##

Bobo 有一个 n 个点，m 条边的有向无环图（即对于任意点 v，不存在从点 v 开始、点 v 结束的路径）。

为了方便，点用 1,2,…,n 编号。 设 count(x,y) 表示点 x 到点 y 不同的路径数量（规定 count(x,x)=0），Bobo 想知道

![x1804.PNG.pagespeed.ic.JZHypanL0G.webp][]

除以 (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

## HINT ##

## Source ##

[湖南省第十二届大学生计算机程序设计竞赛][Link 2]

题解：先计算出 ![gif.latex_5Csum_5E_7Bn_7D_7Bj_3D1_7D_20cout_28i_2Cj_29_b_5Bj_5D][]，这里可以用拓扑排序求出来。最后在乘上a\[ i \]就可以了。先建个反向图，然后从入度为0的点开始，求在该点的后继节点+=ans\[当前节点\] + b\[当前节点\].

AC代码:

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    #define maxn 111111
    typedef long long ll;
    const int mod=1e9+7;
    using namespace std;
    int a[maxn];
    int b[maxn];
    long long ans[maxn];
    struct Edge
    {
        int next; //同一个出发点的另外一条边
        int to; //该条边的终点
        
        //int w;  ///边的权值
        //Edge(){}
       // Edge(int _next,int _to):next(_next),to(_to){}
    }edge[maxn];
    
    int head[maxn]; ///以i为起点的第一条储存边的位置。一般初始化为-1
    int indegree[maxn];
    int cnt;
    
    void addedge(int u,int v /*,int w*/) //添加一条边
    { 
        cnt++;
       //edge[cnt].w=w;
        edge[cnt].to=v;
        edge[cnt].next=head[u];
        head[u]=cnt;
    }
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
    	{
            for(int i=1;i<=n;i++)
    		{
                scanf("%d%d",&a[i],&b[i]);
            }
            memset(head,-1,sizeof head);
            memset(indegree,0,sizeof indegree); //入度 
            memset(ans,0,sizeof ans);
            int u,v;
            cnt=0;
           // int E=0;
            for(int i=1;i<=m;i++) //建图时用反边，倒着计算
    		{   
                scanf("%d%d",&u,&v);
                addedge(v,u);
                //edge[E]=Edge(u,head[v]);
               // head[v]=E++;
                indegree[u]++;       ///统计反向图中的入度
            }
            queue<int> q;
            for(int i=1;i<=n;i++)
            {
            	if(indegree[i]==0)  //入度为0的点加入拓扑序列
    			{  
                    q.push(i);
                }
    		}
            //拓扑排序
            while(!q.empty())
    		{
                int now=q.front();
                q.pop();
                for(int i=head[now];~i;i=edge[i].next) //遍历从now出发的每一条边 
    			{
                    int to=edge[i].to;
                    //ans[后继节点]+=ans[当前节点]+b[当前节点]
                    ans[to]+=(ans[now]+b[now])%mod;
                    ans[to]%=mod;
                    indegree[to]--;
                    if(indegree[to]==0) 
    					q.push(to);
                }
            }
            
            ll res=0;
            for(int i=1;i<=n;i++)
    		{
                res+=(a[i]*ans[i])%mod;
                res%=mod;
            }
            printf("%lld\n",res);
        }
        return 0;
    }

[Link 1]: http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1804
[Submit]: http://acm.csu.edu.cn/OnlineJudge/submitpage.php?id=1804
[Status]: http://acm.csu.edu.cn/OnlineJudge/problemstatus.php?id=1804
[Web Board]: http://acm.csu.edu.cn/OnlineJudge/bbs.php?pid=1804
[x1804.PNG.pagespeed.ic.JZHypanL0G.webp]: http://acm.csu.edu.cn/OnlineJudge/upload/201608/x1804.PNG.pagespeed.ic.JZHypanL0G.webp
[Link 2]: http://acm.csu.edu.cn/OnlineJudge/problemset.php?search=%E6%B9%96%E5%8D%97%E7%9C%81%E7%AC%AC%E5%8D%81%E4%BA%8C%E5%B1%8A%E5%A4%A7%E5%AD%A6%E7%94%9F%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A8%8B%E5%BA%8F%E8%AE%BE%E8%AE%A1%E7%AB%9E%E8%B5%9B
[gif.latex_5Csum_5E_7Bn_7D_7Bj_3D1_7D_20cout_28i_2Cj_29_b_5Bj_5D]: http://latex.codecogs.com/gif.latex?%5Csum%5E%7Bn%7D_%7Bj%3D1%7D%20cout%28i%2Cj%29*b%5Bj%5D