首页 > 代码库 > 1804: 有向无环图
1804: 有向无环图
1804: 有向无环图
Time Limit: 5 Sec Memory Limit: 128 MBSubmit: 341 Solved: 152
[Submit][Status][Web Board]
Description
Bobo 有一个 n 个点，m 条边的有向无环图（即对于任意点 v，不存在从点 v 开始、点 v 结束的路径）。
为了方便，点用 1,2,…,n 编号。 设 count(x,y) 表示点 x 到点 y 不同的路径数量（规定 count(x,x)=0），Bobo 想知道
除以 (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 31 11 11 11 21 32 32 21 00 21 21 22 1500000000 00 5000000001 2Sample Output
44250000014
思路：拓扑排序+dp；
按照拓扑将点权合并就可以了。
1 #include<stdio.h> 2 #include<algorithm> 3 #include<string.h> 4 #include<iostream> 5 #include<math.h> 6 #include<queue> 7 #include<vector> 8 using namespace std; 9 typedef long long LL;10 LL mod = 1e9+7;11 LL dp[100005];12 int cnt[100005];13 LL a[100005];14 LL b[100005];15 vector<int>vec[100005];16 queue<int>que;17 int main(void)18 {19 int n,m;20 while(scanf("%d %d",&n,&m)!=EOF)21 {22 int i,j;LL ask ;23 while(!que.empty())24 que.pop();25 for(i = 0; i < 100005; i++)26 vec[i].clear();27 memset(cnt,0,sizeof(cnt));28 memset(dp,0,sizeof(dp));29 for(i = 1; i <= n; i++)30 {31 scanf("%lld %lld",&a[i],&b[i]);32 }33 while(m--)34 {35 int x,y;36 scanf("%d %d",&x,&y);37 cnt[y]++;38 vec[x].push_back(y);39 }40 for(i = 1; i <= n; i++)41 {42 if(cnt[i] == 0)43 {44 que.push(i);45 }46 }47 while(!que.empty())48 {49 int x = que.front();50 que.pop();51 for(i = 0;i < vec[x].size();i++)52 {53 int y = vec[x][i];54 cnt[y] --;55 if(cnt[y] == 0)56 que.push(y);57 dp[y] = dp[y]+a[x]*b[y]%mod;58 dp[y]%=mod;59 a[y] = a[y] + a[x];60 a[y]%=mod;61 ask = dp[y];62 }63 }ask = 0;64 for(i = 1;i <= n;i++)65 {66 ask = ask + dp[i];67 ask %= mod;68 }69 printf("%lld\n",ask);70 }71 return 0;72 }
1804: 有向无环图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。