首页 > 代码库 > HDU 5195 - DZY Loves Topological Sorting
HDU 5195 - DZY Loves Topological Sorting
题意：
删去K条边，使拓扑排序后序列字典序最大
分析：
因为我们要求最后的拓扑序列字典序最大，所以一定要贪心地将标号越大的点越早入队。我们定义点i的入度为di。
假设当前还能删去k条边，那么我们一定会把当前还没入队的di≤k的最大的i找出来，把它的di条入边都删掉，然后加入拓扑序列。
删除的一定是小连大的边，因为大连小的边在拓扑序列生成的时候就去掉了
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 4 #include <vector> 5 using namespace std; 6 const int MAXN = 100005; 7 int n, m, k, u, v; 8 vector<int> g[MAXN]; 9 int c[MAXN], vis[MAXN], ans[MAXN];10 priority_queue<int> s;11 int main()12 {13 while (~scanf("%d%d%d", &n, &m, &k))14 {15 while (!s.empty()) s.pop();16 for (int i = 1; i <= n; i++) g[i].clear(), vis[i] = c[i] = 0;17 for (int i = 1; i <= m; i++)18 {19 scanf("%d%d", &u, &v);20 g[u].push_back(v);21 c[v]++;22 }23 for (int i = 1; i <= n; i++)24 if (k >= c[i]) s.push(i);25 int cnt = 0;26 while (!s.empty())27 {28 int x = s.top(); s.pop();29 if (c[x] <= k && !vis[x] )30 {31 vis[x] = 1;32 k -= c[x], c[x] = 0;33 ans[cnt++] = x;34 for (int i = 0; i < g[x].size(); i++)35 {36 c[g[x][i]]--;37 if ( !c[g[x][i]] ) s.push(g[x][i]);38 }39 }40 }41 for (int i = 0; i < cnt-1; i++) printf("%d ", ans[i]);42 printf("%d\n", ans[cnt-1]);43 }44 }
HDU 5195 - DZY Loves Topological Sorting
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。