题面

题解

1. 跑一遍拓扑排序求出所有编号在图中的前后关系
2. dist[i]：表示i点在拓扑图中离起点的最远距离(可能存在多起点)，dist[起点] == 100,边的权值为1

代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e4 + 10, M = 2 * N;

int n, m;
int h[N], ne[M], e[M], idx;
int d[N];
int q[N];
int dist[N];


void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

bool topsort() {
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++) {
        if (!d[i]) q[++tt] = i;
    }

    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0) q[++tt] = j;
        }
    }
    if (tt == n - 1) return true;
    else return false;

}

int main() {

    memset(h, -1, sizeof h);
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        add(b, a);
        d[a]++;
    }
    if (topsort()) {
        for (int i = 1; i <= n; i++) dist[i] = 100;
        for (int i = 0; i < n; i++) {
            int j = q[i];
            for (int k = h[j]; k != -1; k = ne[k]) {
                dist[e[k]] = max(dist[e[k]], dist[j] + 1);
            }
        }
        int res=0;
        for(int i=1;i<=n;i++) res+=dist[i];
        cout<<res<<endl;
    } else {
        cout << "Poor Xed" << endl;
    }


    return 0;
}