2021 CCPC 桂林站 E.Buy and Delete Dijsktra 查环+贪心

题目分析

题目大意：

赛后听说没读懂题面卡了一车人，遂感觉大受震撼

给定一张有向图 G G G，初始状态下有 n n n个独立的点，没有任何边。给出 m m m条边及其权值， A l i c e Alice Alice可以从 m m m条边中选择任意数量的边插入图中，但要求插入图中边的总权值和不超过 c c c。

B o b Bob Bob要从图中删边，定义删除操作为：每次从有向图 G G G的边集 S S S中选择一个子边集删除，要求该必须满足该子边集中的边独立存在于图中的时候，整张图是无环的(acyclic：adj.无环的)。

现在 A l i c e Alice Alice希望 B o b Bob Bob删除次数最大化， B o b Bob Bob希望删除次数最小化(废话，就是采取最佳策略)，双方采取最佳策略。求删除轮数。

思路：

刚刚读完题面，第一感觉是背包+贪心，但仔细一想似乎跟背包没啥关系。我们从给图删边的角度入手考虑，如果要求删边操作最大化，那么假设现在有一张完全图，以点数为 3 3 3和 4 4 4为例：

不难发现，第一次可以选择删除满足 u > v u > v u>v的所有边 ( u , v ) (u, v) (u,v)，第二次选择 u < v u < v u d[start][x] + z){ d[start][y] = d[start][x] + z; q.push(make_pair(-d[start][y], y)); } } } } inline void solve(){ memset(d, 0x3f, sizeof(d)); int n, m, c; cin >> n >> m >> c; for(int i = 1; i