自动搬运

查看原文

来自洛谷，原作者为

	yimuhua 其他选手

搬运于2025-08-24 21:43:00，当前版本为作者最后更新于2021-12-28 15:06:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

1. $n$ 个点，$m$ 条边；

2. 边从编号小的连到编号大的，有向无环图；

3. 起点为入度为 $0$ 的点，终点为 $n$；

目标：求所有起点到终点经过的边中经过的最多次数；

策略：

考虑如何计数，发现对于一条边 $(x,y)$ 其被经过时应为从起点到达点 $x$ 后经过该边再从点 $y$ 走到点 $n$，于是可以乘法原理：

1. 建正向图，设 $dp_i$ 为从入度为 $0$ 的点到达点 $i$ 的方案数，则：

   dp[next] += dp[cur];
   

2. 建正向图，设 $dp2_i$ 为从点 $n$ 到达点 $i$ 的方案数，则：

   dp2[next] += dp2[cur];
   

3. 枚举每一条边 $(x, y)$，设编号为 $i$，则：

   maxi = max(maxi, dp[i] * dp2[i]);
   

AC代码：

#include <bits/stdc++.h>
using namespace std;
queue<int> q, q2;
vector<int> nbr[5005], nbr2[5005];
int n, m, maxi, dp[5005], dp2[5005], in[5005], in2[5005], u[50005], v[50005];
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
        nbr[u[i]].push_back(v[i]);
        nbr2[v[i]].push_back(u[i]);
        in[v[i]]++, in2[u[i]]++;
    }
    for(int i = 1; i <= n; i++)
        if(!in[i])
            dp[i] = 1, q.push(i);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(int i = 0; i < nbr[x].size(); i++) {
            in[nbr[x][i]]--;
            dp[nbr[x][i]] += dp[x];
            if(!in[nbr[x][i]])
                q.push(nbr[x][i]);
        }
    }
    dp2[n] = 1;
    q2.push(n);
    while(!q2.empty()) {
        int x = q2.front();
        q2.pop();
        for(int i = 0; i < nbr2[x].size(); i++) {
            in2[nbr2[x][i]]--;
            dp2[nbr2[x][i]] += dp2[x];
            if(!in2[nbr2[x][i]])
                q2.push(nbr2[x][i]);
        }
    }
    for(int i = 1; i <= m; i++)
        maxi = max(maxi, dp[u[i]] * dp2[v[i]]);
    cout << maxi;
    return 0;
}