\(\color{#0066ff}{ 题目描述 }\)
给定一个有向图，改变其中某些边的方向，它将成为一个有向无环图。
现在求一个改变边方向的方案，使得所选边边权的最大值最小。
\(\color{#0066ff}{输入格式}\)
点数n，边数m，接下来是m条有向边
\(\color{#0066ff}{输出格式}\)
输出一个最大值，一个k
接下来一行k个数，表示那些边需要反向
\(\color{#0066ff}{输入样例}\)
5 62 1 15 2 62 3 23 4 34 5 51 5 4 5 72 1 53 2 31 3 32 4 14 3 55 4 11 5 3
\(\color{#0066ff}{输出样例}\)
2 21 3 3 33 4 7
\(\color{#0066ff}{数据范围与提示}\)
\(2 \leq n \leq 100000\), \(1 \leq m \leq 100000\)
\(\color{#0066ff}{ 题解 }\)
根据题目，显然要二分答案
考虑二分答案之后怎么做
对于比mid大的边，我们肯定是不能改变方向的
于是直接加入图中
然后只需看看有没有环就行了，因为比mid小的边我们可以任意更改
可以用拓扑排序做
因为它只让最大值最小，并没有说改变边的数量最小，所以小的边随便改
现在考虑输出方案
我们在拓扑排序的时候记一下每个点的拓扑序
考虑一条边x到y，如果x的拓扑序大于y，显然可能成环（不是一定成环）
但是如果x的拓扑序小于y，一定不会成环
题目有不限制改边数量，我们就将其反向即可
#include#define LL long longLL in() { char ch; LL x = 0, f = 1; while(!isdigit(ch = getchar()))(ch == '-') && (f = -f); for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48)); return x * f;}const int maxn = 1e5 + 10;struct node { int x, y, z, id; friend bool operator < (const node &a, const node &b) { return a.z < b.z; }}e[maxn];struct E { int to; E *nxt; E(int to = 0, E *nxt = NULL): to(to), nxt(nxt) {}}pool[maxn], *tail;int du[maxn], top[maxn];bool vis[maxn];int n, m;E *head[maxn];void add(int from, int to) { head[from] = new E(to, head[from]);} bool ok(int mid) { std::queue q; int cnt = 0; tail = pool; for(int i = 1; i <= n; i++) du[i] = 0, head[i] = NULL, top[i] = 0; for(int i = 1; i <= m; i++) vis[i] = false; for(int i = m; i >= 1; i--) { if(e[i].z <= mid) break; add(e[i].x, e[i].y); du[e[i].y]++; } for(int i = 1; i <= n; i++) if(!du[i]) q.push(i); while(!q.empty()) { int tp = q.front(); q.pop(); top[tp] = ++cnt; for(E *i = head[tp]; i; i = i->nxt) { du[i->to]--; if(!du[i->to]) q.push(i->to); } } if(cnt != n) return false; for(int i = 1; i <= m; i++) { if(e[i].z > mid) break; if(top[e[i].x] > top[e[i].y]) vis[e[i].id] = true; } return true;} int main() { n = in(), m = in(); for(int i = 1; i <= m; i++) e[i].x = in(), e[i].y = in(), e[i].z = in(), e[i].id = i; std::sort(e + 1, e + m + 1); int l = 0, r = 1e9; int ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(ok(mid)) ans = mid, r = mid - 1; else l = mid + 1; } ok(ans); int tot = 0; for(int i = 1; i <= m; i++) if(vis[i]) tot++; printf("%d %d\n", ans, tot); for(int i = 1; i <= m; i++) if(vis[i]) printf("%d ", i); return 0;}