NC201607 DDOS
题意：
题意有点抽象，翻译一下n个点，m条边，求1号点有多少种方式到达n号点
做法：
实际上就是求一个拓扑序，首先将入度为0的点入队，然后在遍历的同时，判断是否新增了入度为0的点即可。对于每个分支，都增加当前点的方法数，最后答案就是n号点的值
代码：
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e5 + 5;
const ll mod = 20010905;
struct edge
{
int to;
ll w;
int nex;
}e[MAXN * 4];
int head[MAXN], tot;
void init(int n)
{
fill(head, head + n + 1, -1);
tot = 1;
}
void add(int a, int b, ll c)
{
e[tot] = edge{ b,c,head[a] };
head[a] = tot++;
}
int du[MAXN];
ll ans[MAXN];
int main()
{
int n, m;
sc("%d%d", &n, &m);
init(n);
for (int i = 0; i < m; i++)
{
int a, b;
ll c;
sc("%d%d%lld", &a, &b, &c);
add(a, b, c);
du[b]++;
}
queue<int>q;
for (int i = 1; i <= n; i++)
{
if (du[i] == 0)
q.push(i);
}
ans[1] = 1;
while (!q.empty())
{
int t = q.front();
q.pop();
for (int i = head[t]; i + 1; i = e[i].nex)
{
int v = e[i].to;
ans[v] = (ans[v] + ans[t]) % mod;
du[v]--;
if (du[v] == 0)
q.push(v);
}
}
pr("%lld\n", ans[n] % mod);
} 
查看6道真题和解析
