P2883

yimuhua · 2021-12-28 15:06:22 · 题解

题意：

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;
}