物流运输 有哪些网站可以做推广,营销型网站传统网站,网站关键词从哪改,招设计师在哪里找Bobo 有一个 n 个点#xff0c;m 条边的有向无环图#xff08;即对于任意点 v#xff0c;不存在从点 v 开始、点 v 结束的路径#xff09;。为了方便#xff0c;点用 1,2,…,n 编号。 设 count(x,y) 表示点 x 到点 y 不同的路径数量#xff08;规定 count(x,x)0#xff…Bobo 有一个 n 个点m 条边的有向无环图即对于任意点 v不存在从点 v 开始、点 v 结束的路径。 为了方便点用 1,2,…,n 编号。 设 count(x,y) 表示点 x 到点 y 不同的路径数量规定 count(x,x)0Bobo 想知道 除以 (10 97) 的余数。 其中a i,b j 是给定的数列。 Input 输入包含不超过 15 组数据。 每组数据的第一行包含两个整数 n,m (1≤n,m≤10 5). 接下来 n 行的第 i 行包含两个整数 a i,b i (0≤a i,b i≤10 9). 最后 m 行的第 i 行包含两个整数 u i,v i代表一条从点 u i 到 v i 的边 (1≤u i,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 2Sample Output 4
4
250000014Hint 思路 由有向图拓扑序的性质可以知道拓扑序在后的节点是没有指向拓扑序在前的节点。 那么我们在对整个图进行拓扑的时候把起始点 x 的a[x] 值 附加到 这个边的终点 y 的a[y] 值上。 并且对于每一个边我们维护一个 long long 类型的 答案 ansans a[x]*b[y] ( 边 是 x ~ y ) 那么这里就介绍刚刚我们为什么要附加数值a[x] 到a[y]上。 如果由三个点 x y z ,由如下的连接关系 x ~ y ~ z 那么x到y的边我们会算一次对答案的贡献值y到z的边我们也会算一次。 还有一个x到z的边我们仍然需要算。因为x可以到达z那么如果我们在拓扑的时候把a[y]加上a[x] 时 我们在算 b到z 的边的时候就顺便的加上了a到z的边。 因为x 的拓扑优先级比y高并且x可以到达y那么x就可以到达y能到达的所有边那么就解释了这样做的原因。 这样做的时间复杂度就会转化为 O ( N ) 主要是理解后就很好写代码可以自己动手画图理解一下上面 讲的内容。 实现细节见ac代码 #include iostream
#include cstdio
#include cstring
#include algorithm
#include cmath
#include queue
#include stack
#include map
#include set
#include vector
#include iomanip
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf(%I64d,x)
#define xll(x) printf(%I64d\n,x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int ix;in;i)
#define repd(i,x,n) for(int ix;in;i)
#define pii pairint,int
#define pll pairlong long ,long long
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), \0, sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(x)
#define db(x) cout [ x ] endl;
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans1;while(b){if(b%2)ansans*a%MOD;aa*a%MOD;b/2;}return ans;}
inline void getInt(int* p);
const int maxn100010;
const int inf0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
std::vectorint son[maxn];
const ll mod1e97ll;
ll ans0ll;
ll a[maxn];
ll b[maxn];
ll num[maxn];
int du[maxn];
int main()
{// freopen(D:\\common_text\\code_stream\\in.txt,r,stdin);//freopen(D:\\common_text\\code_stream\\out.txt,w,stdout);gbtb;int n,m;while(cinnm){repd(i,1,n){son[i].clear();}MS0(du);MS0(num);repd(i,1,n){cina[i]b[i];}int x,y;repd(i,1,m){cinxy;son[x].push_back(y);du[y];}queueint q;repd(i,1,n){if(!du[i]){q.push(i);}}ans0ll;while(q.size()){int tempq.front();q.pop();for(auto x:son[temp]){ans(ans(a[temp]*b[x])%modmod)%mod;a[x]a[temp];a[x](a[x]mod)%mod;du[x]--;if(!du[x]){q.push(x);}}}coutansendl;}return 0;
}inline void getInt(int* p) {char ch;do {ch getchar();} while (ch || ch \n);if (ch -) {*p -(getchar() - 0);while ((ch getchar()) 0 ch 9) {*p *p * 10 - ch 0;}}else {*p ch - 0;while ((ch getchar()) 0 ch 9) {*p *p * 10 ch - 0;}}
} 转载于:https://www.cnblogs.com/qieqiemin/p/10679978.html
