You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
62 lines
1.5 KiB
62 lines
1.5 KiB
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 10010, M = 30010;
|
|
int din[N]; //记录每个节点入度
|
|
int dist[N]; //记录每个节点距离起点的最小值
|
|
int cnt[N]; // cnt[i]记录以节点i为终点的路径的边数
|
|
bool st[N];
|
|
queue<int> q;
|
|
int n, m;
|
|
//邻接表
|
|
int e[M], h[N], idx, w[M], ne[M];
|
|
void add(int a, int b, int c) {
|
|
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
|
|
}
|
|
|
|
bool spfa() {
|
|
memset(dist, -0x3f, sizeof dist);
|
|
q.push(0);
|
|
st[0] = true;
|
|
dist[0] = 0;
|
|
|
|
while (q.size()) {
|
|
int u = q.front();
|
|
q.pop();
|
|
st[u] = false;
|
|
|
|
for (int i = h[u]; ~i; i = ne[i]) {
|
|
int j = e[i];
|
|
if (dist[j] < dist[u] + w[i]) {
|
|
dist[j] = dist[u] + w[i]; //最长路,判正环
|
|
cnt[j] = cnt[u] + 1;
|
|
if (cnt[j] > n + 1) return false;
|
|
if (!st[j]) {
|
|
q.push(j);
|
|
st[j] = true;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
int main() {
|
|
memset(h, -1, sizeof h);
|
|
scanf("%d %d", &n, &m);
|
|
while (m--) {
|
|
int a, b;
|
|
scanf("%d %d", &a, &b);
|
|
add(b, a, 1);
|
|
}
|
|
|
|
//超级源点0号点
|
|
for (int i = 1; i <= n; i++) add(0, i, 100);
|
|
|
|
if (spfa()) {
|
|
int res = 0;
|
|
for (int i = 1; i <= n; i++) res += dist[i];
|
|
printf("%d\n", res);
|
|
} else
|
|
puts("Poor Xed");
|
|
return 0;
|
|
} |