1804: 有向無環(huán)圖

Submit Page? ??? Summary? ??? Time Limit:?5 Sec???? ? Memory Limit:?128 Mb???? ? Submitted:?732???? ? Solved:?305????

---

Description

Bobo 有一個 n 個點，m 條邊的有向無環(huán)圖（即對于任意點 v，不存在從點 v 開始、點 v 結束的路徑）。 為了方便，點用 1,2,…,n 編號。 設 count(x,y) 表示點 x 到點 y 不同的路徑數量（規(guī)定 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 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 #include<iostream> #include<cstring> #include<cstdio> #include<queue> #define MOD 1000000007 #define MAX 100005 //數組開的太大了，我用的是codeblocks導致一直運行不了，后來發(fā)現數組開大了，定義為全局變量就好， //全局變量是存儲在數據區(qū)的，而局部變量是用棧存儲的，棧太小，會溢出 using namespace std; vector<int> list[MAX]; long long a[MAX],b[MAX]; int degree[MAX]; long long sum[MAX]; int main() {int n,m;while(~scanf("%d%d",&n,&m)){memset(degree,0,sizeof(degree));memset(list,0,sizeof(list));memset(sum,0,sizeof(sum));for(int i=1; i<=n; i++){scanf("%lld%lld",&a[i],&b[i]);sum[i]=b[i];}for(int i=1; i<=m; i++){int fa,son;scanf("%d%d",&fa,&son);degree[fa]++;//記錄從fa出發(fā)的路徑數list[son].push_back(fa);//記錄到son的點}queue<int> original;queue<int> sorted;for(int i=1; i<=n; i++){if(degree[i]==0)original.push(i);//沒有出度的入隊}while(!original.empty())//隊列不為空{int son=original.front();//讀取最底端元素original.pop();//出隊(先進先出)取出最底端元素for(int i=0; i<list[son].size(); i++){int fa=list[son][i];degree[fa]--;if(degree[fa]==0)original.push(fa);}sorted.push(son);}long long ans=0;while(!sorted.empty())//隊列不為空{int son=sorted.front();sorted.pop();/*eg:4 41 11 11 11 11 21 32 31 4出隊的順序是3 4 2 1這樣子的話首先計算的是以3為終點的路徑，分別是1->3,2->31->3:ans=ans+a[1]*b[3]=1;b[1]=b[1]+b[3]=2;2->3:ans=ans+a[2]*b[3]=2;b[2]=b[2]+b[3]=2;接著就是1->4:ans=ans+a[1]*b[4]=3;b[1]=b[1]+b[4]=3;然后1->2:ans=ans+a[1]*b[2]=5;b[1]=b[1]+b[2]=5;從數據可以看出算1->2的時候其實是這樣子算的，首先加上原來累加的，其次b[2]=b[2]+b[3],這樣是因為1->2->3也可以這樣子認為1->3的時候只計算了一次b[3],到1->2的時候要多加一個b[3],這個地方一開始想錯了，以至于鉆了好久的牛角尖，還是得自己慢慢領悟吧！*/for(int i=0; i<list[son].size(); i++){int fa=list[son][i];ans=(ans+(a[fa]*sum[son])%MOD)%MOD;sum[fa]=(sum[fa]+sum[son])%MOD;}}printf("%lld\n",ans%MOD);}return 0; }

總結

以上是生活随笔為你收集整理的CSU 1804的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。