题目链接
题意 【#|Codeforces Round #532 (Div. 2) E. Andrew and Taxi（二分+拓扑排序）】给你一个图1-n标号，m条有向边。
每条有向边有一个权值，代表翻转其方向所需代价。
求使得图变成无环图，翻转边权的最大值最小。
思路 二分答案，判断权值大于答案的边集是否能成环，如果不能说明答案可以再小点，否则答案可以大点。
关键是翻转哪些边比较难想，第一次感受到拓扑排序，排序二字用处。
按拓扑排序的顺序，给每个点从小到大赋权，最后判断如果起点权值大于终点权值则需要翻转。
关于评论疑惑，猜测拓扑排序应该满足一个性质
如果一个图所有边的top[u] < top[v]，则该图无环，top[]表示1-n的一种排列，u表示起点，v表示终点。
画个图就感受到了？
所以这题先二分构造一个答案最小的top序列，然后选择翻转某些边满足top[u] < top[v]
代码
#include
using namespace std;
int n, m;
int sum, in[100005], top[100005];
vector e[100005], path;
struct Node
{
int u, v, w;
}data[100005];
int f(int mid)
{
sum = 0;
for(int i = 1;
i <= n;
++i) e[i].clear();
memset(in,0,sizeof(in));
for(int i = 1;
i <= m;
++i)
{
if(data[i].w > mid)
{
e[data[i].u].push_back(data[i].v);
++in[data[i].v];
}
}
queue q;
for(int i = 1;
i <= n;
++i) if(!in[i]) q.push(i), top[i] = ++sum;
while(!q.empty())
{
int u = q.front();
q.pop();
for(auto v : e[u])
{
--in[v];
if(!in[v]) q.push(v), top[v] = ++sum;
}
}for(int i = 1;
i <= n;
++i) if(in[i]) return 0;
return 1;
}int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;
i <= m;
++i) scanf("%d%d%d",&data[i].u,&data[i].v,&data[i].w);
int l = 0, r = 1e9, mid, ans;
while(l <= r)
{
mid = (l+r) >> 1;
if(f(mid)) r = mid-1, ans = mid;
else l = mid+1;
}
f(ans);
// 每个点top都有值，且必定能够通过翻转某些边得到当前top值
for(int i = 1;
i <= m;
++i) if(data[i].w <= ans && top[data[i].u] > top[data[i].v]) path.push_back(i);
printf("%d %d\n",ans,path.size());
for(auto i : path) printf("%d ",i);
return 0;
}
推荐阅读
- 数据结构和算法|LeetCode 的正确使用方式
- #|7.分布式事务管理
- #|算法设计与分析（Java实现）——贪心算法（集合覆盖案例）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #|阿尔法点亮LED灯(一）汇编语言
- #|Multimedia
- #|ARM裸机开发（汇编LED灯实验（I.MX6UL芯片））
- 基础课|使用深度优先搜索（DFS）、广度优先搜索（BFS）、A* 搜索算法求解 (n^2 -1) 数码难题，耗时与内存占用（时空复杂度）对比（附（(n^2 - 1) 数码问题控
- #|学习笔记 | Ch05 Pandas数据清洗 —— 缺失值、重复值、异常值
- win10|搏一搏 单车变摩托，是时候捣鼓一下家中的小米电视机啦。