给定一个有向图，改变其中某些边的方向，它将成为一个有向无环图。
现在求一个改变边方向的方案，使得所选边边权的最大值最小。
点数n，边数m，接下来是m条有向边
第一行输出两个值，一个所选边权最小值和边数k
接下来一行k个编号，表示那些边需要反向
输入样例
5 6
2 1 1
5 2 6
2 3 2
3 4 3
4 5 5
1 5 4
5 7
2 1 5
3 2 3
1 3 3
2 4 1
4 3 5
5 4 1
1 5 3
输出样例
2 2
1 3
3 3
3 4 7
题解：
二分，每次取到一个 mid ，只保留长度大于 mid 的边
dfs判环，若有环，说明 ans>mid ，否则 ans≤mid
找到 ans 后，对长度大于 ans 的边进行一次拓扑排序，对多余的点直接接在拓扑排序序列后面即可
对从 x 到 y 的长度 ≤ans 的边，如果 x 在拓扑排序序列中的位置比 y 后，则这条边需取反
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
int n, m, maxl = 0, indeg[N], b[N], t;
int head[N], edge[N], leng[N], nxt[N], from[N];
vector<int> ans;
bool v[N], w[N];
queue<int> q;
void add(int x, int y, int z, int i) {
edge[i] = y;
leng[i] = z;
nxt[i] = head[x];
head[x] = i;
from[i] = x;
}
bool dfs(int x, int now) {
v[x] = 1; w[x] = 1;
for (int i = head[x]; i; i = nxt[i]) {
int y = edge[i], z = leng[i];
if (z <= now) continue;
if (w[y] || !dfs(y, now)) return 0;
}
w[x] = 0;
return 1;
}
inline bool check(int now) {
memset(v, 0, sizeof(v));
memset(w, 0, sizeof(w));
for (int i = 1; i <= n; i++)
if (!v[i] && !dfs(i, now)) return 0;
return 1;
}
void topsort(int now) {
for (int i = 1; i <= n; i++)
if (!indeg[i]) q.push(i);
while (q.size()) {
int x = q.front();
q.pop();
b[x] = ++t;
for (int i = head[x]; i; i = nxt[i]) {
int y = edge[i], z = leng[i];
if (z > now && !--indeg[y]) q.push(y);
}
}
}
int work(int now) {
for (int i = 1; i <= m; i++) {
int y = edge[i], z = leng[i];
if (z > now) ++indeg[y];
}
topsort(now);
for (int i = 1; i <= n; i++)
if (!b[i]) b[i] = ++t;
for (int i = 1; i <= m; i++) {
int x = from[i], y = edge[i], z = leng[i];
if (z <= now && b[x] > b[y]) ans.push_back(i);
}
return ans.size();
}
int main() {
cin >> n >> m;
for (int i = 1, x, y, z; i <= m; i++) {
scanf("%d%d%d", &x, &y, &z);
add(x, y, z, i); maxl = max(maxl, z);
}
int l = 0, r = maxl;
while (l < r) {
int mid = (l + r) >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << " " << work(l) << endl;
for (int i = 0; i < ans.size(); i++) printf("%d ", ans[i]);
return 0;
}
CF1100E Andrew and Taxi 二分答案 + 拓扑排序
原文：https://www.cnblogs.com/Paranoid-LS/p/11246821.html