题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=5695
思路
给定一些关系 进行拓扑排序 但是有一个要求 对于哪些没有确切的位置的点 要按照ID大小 ID大的排在前面 这个就可以用 优先队列
如果不用优先队列 而是每次从大到小去遍历 是不可行的
因为 可能存在 一个点出队后 然后后面有点入队 这个点的ID比当前已经在队伍中的点的ID要大 那么这个点要比那个点先出队
AC代码
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)) #define pb push_back #define bug puts("***bug***"); #define fi first #define se second //#define bug //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double E = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const int maxn = 1e5 + 10; const int MOD = 1e9 + 7; vector <int> edge[maxn]; int du[maxn]; int n, m; ll tot; void toposort() { priority_queue <int> q; for (int i = 1; i <= n; i++) if (du[i] == 0) q.push(i); int Min = INF; while (!q.empty()) { int u = q.top(); q.pop(); Min = min(Min, u); tot += Min; int len = edge[u].size(); for (int i = 0; i < len; i++) if ((--du[edge[u][i]]) == 0) q.push(edge[u][i]); } } void clear() { for (int i = 1; i <= n; i++) { edge[i].clear(); du[i] = 0; } } int main() { int t; cin >> t; while (t--) { scanf("%d%d", &n, &m); clear(); int x, y; for (int i = 0; i < m; i++) { scanf("%d%d", &x, &y); du[y]++; edge[x].pb(y); } tot = 0; toposort(); printf("%lld\n", tot); } }转载于:https://www.cnblogs.com/Dup4/p/9433085.html
相关资源：JAVA上百实例源码以及开源项目