DDoS

NC201607. DDoS

描述

Nancy的男朋友喜欢网络安全！
最近，一种新的DDoS——脉冲波悄然来临。其基本原理是利用不同线路服务器的延时，使得Request同时到达目标服务器，以堵塞其它正常的通讯。
不妨假设攻击者在1号节点，目标服务器在$n$号节点，其余节点（2到n-1号节点）为中继服务器。
攻击者可以在任意时间发送一个定向数据包（即规定其经过中继服务器的路线，但不同数据包的路线不能完全相同），目标服务器对这种数据包具有100%的识别率，一旦识别到这种数据包，则会屏蔽这一时刻后的所有数据包。
Nancy好奇，攻击者在最优策略下，目标服务器能够收到多少份数据包呢？

输入描述

第一行：两个整数n,m。
接下来m行：每行三个整数x,y,z，表示节点x与y可以单向通信（x到y），耗时为z。
数据满足：，，图为拓扑图（有向无环图）。

输出描述

共一行：表示攻击者在最优策略下，目标服务器能够收到数据包的数量。
由于数量可能会很大，你只需要输出答案对20010905取模后的值。

示例1

输入:

输出:

说明:

显然，攻击者在0时刻发送两个定向数据包（1-2-4和1-3-4），它们同时在第4时刻到达目标服务器。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 112ms, 内存消耗: 6756K, 提交时间: 2020-01-18 21:39:18

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int MD=20010905;
vector<int> G[N];
int in[N],f[N];
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0,u,v;i<m;i++) {
		scanf("%d%d%*d",&u,&v);
		G[u].push_back(v);
		in[v]++;
	}
	f[1]=1;
	queue<int> qu;
	qu.push(1);
	while(!qu.empty()) {
		int u=qu.front();
		qu.pop();
		for(int i=0;i<G[u].size();i++) {
			int v=G[u][i];
			f[v]=(f[v]+f[u])%MD;
			if(--in[v]==0) qu.push(v);
		}
	}
	printf("%d\n",f[n]);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 68ms, 内存消耗: 15944K, 提交时间: 2020-08-09 21:45:07

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,mod=20010905;
int n,m,f[N];
vector<int>v[N];
int dfs(int x){
	if(f[x])return max(f[x],0);
	for(int i=0;i<v[x].size();i++){
		f[x]=(f[x]+dfs(v[x][i]))%mod;
	}
	if(!f[x])f[x]=-1;
	return max(f[x],0);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		v[x].push_back(y);
	}
	f[n]=1;
	printf("%d\n",dfs(1));
	return 0;
}