拓扑排序。每次找到入度为0的点存下来。一次找完后，对这些点计算费用。
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; vector<int>abc[10005]; int rudu[10005]; int linshi[10005]; int main() { int n, m, i, x, y, k; while (~scanf("%d%d", &n, &m)) { int sum = 0; for (i = 0; i < 10003; i++) abc[i].clear(); memset(rudu, 0, sizeof(rudu)); for (i = 0; i < m; i++) { scanf("%d%d", &x, &y); rudu[x]++; abc[y].push_back(x); } int fei = 0; int ans = 0; while (1) { if (sum == n) break; int uuu = 0;//标记有没有找到 int yy = 0; for (i = 1; i <= n; i++) { if (rudu[i] == 0) { rudu[i]--; uuu = 1;//找到了 sum++; linshi[yy] = i; yy++; } } if (uuu == 0) break; for (i = 0; i < yy; i++) { ans = ans + fei; for (k = 0; k < abc[linshi[i]].size(); k++) rudu[abc[linshi[i]][k]]--; } fei++; } if (sum == n) { ans = ans + n * 888; printf("%d ", ans); } else if (sum != n) printf("-1 "); } return 0; }