一篇题解

# Pashmak and Graph

# 题面翻译

给定 $n$ 个点，$m$ 条带权边的有向图。
现在请你找一条路径，起点和终点自取，在保证路径上的边权严格递增（即
下一条边的 v 严格大于上一条的 v）的情况下包含最多的边。
每条边只用一次。请输出路径最多能包含多少条边。

第一行输入 2 个数字 $n$ , $m$ , 表示 $n$ 个点 $m$ 条有向边。
第 2 到 $m+1$ 行每行 3 个数 $s,t$ 和 $v$ ，表示边的起点、终点、边权。

# 分析

xxxxxxxxxx #include<cstring>#include<iostream>#include<algorithm>​using namespace std;​#define int long long​const int N = 1e6 + 10, mod = 1e9 + 7;​int n, h, w;int fac [N], inv [N];int dp [N];​struct pos {    int x, y;} a [N];​inline void read (int &a){    int x = 0,f = 1;    char ch = getchar ();    while (ch > '9' || ch < '0')   {        if (ch == '-')            f = -1;        ch = getchar ();   }​    while (ch >= '0' && ch <= '9')        x = x * 10 + ch - '0',ch = getchar ();    a = x * f;}​inline int qmi (int a,int k){    int res = 1;​    while (k)   {        if (k & 1)            res = res * a % mod;        a = a * a % mod;        k >>= 1;   }​    return res;}​bool cmp (pos b, pos c)   {   // 按照横坐标排序，因为发现我们的式子在横坐标排序后    // 如果前面的那个点的纵坐标小于后面的点实际上是没有影响的，而且在后面进行取出点的时候也是会检查是否为合法点    if (b.x == c.x)        return b.y < c.y;    return b.x < c.x;}​inline int C (int a,int b){    return fac [a] * inv [a - b] % mod * inv [b] % mod;}​signed main (){    read (h), read (w), read (n);​    for (register int i = 1 ; i <= n ; i ++ )   {        int x, y;        read (x), read (y);        a [i].x = x - 1, a [i].y = y -1;   }​    a [++ n] = (pos) {h - 1, w - 1};    sort (a + 1, a + n + 1, cmp);        fac [0] = inv [0] = 1;​    for (register int i = 1 ; i <= 3e5 + 10 ; i ++ )   {        fac [i] = fac [i - 1] * i % mod;        inv [i] = qmi (fac [i], mod - 2);   }        for (register int i = 1 ; i <= n ; i ++ )   {        int x = a [i].x ,y = a [i].y;        dp [i] = C (x + y, x);                for (register int j = 1 ; j < i ; j ++ )       {            if (a [j].y <= y && a [j].x <= x)           {                int xx = x - a [j].x;                int yy = y - a [j].y;                //cout<<xx<<""<<yy<<endl;                dp [i] = (dp [i] - dp [j] * C (xx + yy, xx) % mod + mod) % mod;                //cout<<dp [i]<<endl;           }       }   }        printf ("% lld", dp [n] % mod);​    return 0;} cpp

那么我们现在只需要怎么转移即可了。其实这一步也非常简单。对于一个出点，他的值要么是走当前这条边，要么是从别的边转移过来。那么我们的转移方程就出来了。 $f_v = max(f_v, f_u + 1)$。其中 $v$ 是出点， $u$ 是入点。

还有一个小细节是我们这个图是可能会有重边的，那么我们可以直接开一个临时数组，把他们先存一下，然后一起转移即可。

下面是代码实现

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstring>

using namespace std;

inline int read()

{

    int x = 0, f = 1;

    char ch = getchar();

    while(ch > '9' || ch < '0')

    {

        if(ch == '-')

            f = -1;

        ch = getchar();

    }

    while(ch >= '0' && ch <= '9')

        x = x * 10 + ch - '0', ch = getchar();

    return x * f;

}

inline void write(int x)

{

    if(x < 0)

    {

        x = -x;

        putchar('-');

    }

    if(x > 9)

        write(x / 10);

    putchar(x % 10 + '0');

}

const int N = 1e6 + 10;

int n, m;

int f[N], g[N];   //f []: 答案  g []：重边的处理

int stk[N], cnt;    // 存放重边

int res = 0;

struct Edge

{

    int u, v, w;

    bool operator < (const Edge& a) {return w < a.w;}

} e[N];

int main()

{

    n = read(), m = read();

    for(register int i = 1 ; i <= m ; i ++ )

    {

        e[i].u = read(), e[i].v = read(), e[i].w = read();

    }

    sort(e + 1, e + m + 1);

    for(register int i = 1 ; i <= m ; i ++ )

    {   

        int j = i - 1;  // 到最左边的相同的边的位置

        while(e[++ j].w == e[i].w)   // 将所有重边进行转移

        {

            stk[++ cnt] = e[j].v;

            g[e[j].v] = max(g[e[j].v], f[e[j].u] + 1);   // 临时存一下重边的状态

        }

        while(cnt)

        {

            f[stk[cnt]] = max(f[stk[cnt]], g[stk[cnt]]);   // 用重边更新当前枚举的边

            g[stk[cnt]] = 0;  // 清空临时数组

            cnt --;

        }

        i = j - 1;   // 因为我们已经处理了所有的重边，那么就直接跳过这些重边即可

    }

    for(register int i = 1 ; i <= n ; i ++ )

    {

        res = max(res, f[i]);

    }

    write(res);

    return 0;

}

又水了一道题。★,°:.☆(￣▽￣)/$:.°★ 。