【牛客小白月赛21】NC201607 DDoS 题目链接

明明是道水题，为什么如此fake。。qwq

题目描述越看越糊涂，大致意思就是有一个拓扑图（有向无环图），1号点可以在任意时间发送一个定向数据包到n号点（即路径可以你自己规定，到达n号点的所用时间为路径上的边权和），但n号点只要在某一时间收到数据包后就不会再收后面的数据包了。问最优策略下能够收到多少份数据包，即求最多有多少个数据包同时到达n号点。

跟着题意绕来绕去，看了别的题解才知道这几段话的重点：可以在任意时间发送！也就是说对于1到n的所有路径，尽管所用时间不同，可你完全可以通过调整他们的开始时间，使他们最后在同一时间到达。也就是说，所有路径都可以在同一时间到达！所有路径都是答案！

即求1到n的路径数，用拓扑排序或记忆化搜索都可，而且。。边权z没有任何作用（看别的题解说这里给了个奇怪的数据范围就是在暗示qwq）

方法一：记忆化搜索

#include<cstdio>
using namespace std;
#define max(a,b) (a>b ? a:b)
const int p=20010905;
inline int rd() {
    char ch=getchar();
    int x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
struct edge {
    int v,h;
} e[200005];
int h[100005],n,m,tot;
int f[100005];

inline void add(int u,int v) {
    e[++tot]=(edge) {
        v,h[u]
    },h[u]=tot;
}

int dfs(int u) {
    if (f[u]!=0) return max(f[u],0);//记忆化搜索：f[u]为-1或正数直接返回
    for (int i=h[u]; i; i=e[i].h)
        f[u]=(f[u]+dfs(e[i].v))%p;
    if (!f[u]) f[u]=-1;//如果走过但是答案为0就标记-1，防止下次再走
    return max(f[u],0);
}

int main() {
    scanf("%d%d",&n,&m);
    for (int u,v,z; m; m--)
        u=rd(),v=rd(),z=rd(),add(u,v);
    f[n]=1;
    printf("%d",dfs(1));
}

方法二：拓扑排序

#include<cstdio>
using namespace std;
#define max(a,b) (a>b ? a:b)
const int p=20010905;
struct edge {
    int v,h;
} e[200005];
int h[100005],r[100005],n,m,tot;
int q[100005],head,tail,f[100005];

inline int rd() {
    char ch=getchar();
    int x=0;
    while(ch<'0' || ch>'9') ch=getchar();
    while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}

inline void add(int u,int v) {
    e[++tot]=(edge) {
        v,h[u]
    },h[u]=tot;
}

int main() {
    scanf("%d%d",&n,&m);
    for (int u,v,z; m; m--)
        u=rd(),v=rd(),z=rd(),r[v]++,add(u,v);
    f[1]=q[tail=1]=1;
    while(head<tail){
        int u=q[++head];
        for (int i=h[u],v; i; i=e[i].h){
            v=e[i].v,r[v]--;
            if (!r[v]) q[++tail]=v;
            f[v]=(f[v]+f[u])%p;
        }
    }
    printf("%d",f[n]);
}