CF1100E Andrew and Taxi 题解

题目链接：Andrew and Taxi

题意：

给定一个 \(n\) 个点 \(m\) 条边的有向图，边有权值 \(w_i\) 。

要求改变其中某些边的方向，使其成为一个有向无环图。

现在求一个改变边方向的方案，使得所选边边权的最大值最小。

数据范围：

\(1 \le n,m \le 10^5,~1 \le w_i \le 10^9\) 。

考虑二分边权的最大值 \(x\) ，那么现在所有边分成了两种

1. 边权 \(w_i\) 小于等于 \(x\) 的边
2. 边权 \(w_i\) 大于 \(x\) 的边

显然，如果第二种边构成了环，那么这种情况是不行的。

考虑拓扑排序判环，顺便记录一下每个点的拓扑序。

那么需要翻转的第一种边 \(u_i \to v_i\) 一定有 \(T(v_i) < T(u_i)\) ，其中 \(T\) 表示节点的拓扑序。

于是这道题就做完了，还是蛮简单的。结果我连拓扑排序判环都没想到，很少用。

时间复杂度 \(\mathcal{O}(n \log m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(1e5 + 15))

int n, m, val[N], in[N], topo[N];
vector<int> ans, vec[N];
struct Edge { int u, v, w; } e[N];
bool check(int x)
{
    rep(i, 1, n) { in[i] = topo[i] = 0; vec[i].clear(); }
    rep(i, 1, m) if(e[i].w > x) { vec[e[i].u].pb(e[i].v); ++in[e[i].v]; }
    static queue<int> q; q = {}; int cnt = 0;
    rep(i, 1, n) if(!in[i]) q.push(i);
    while(!q.empty())
    {
        int u = q.front(); q.pop(); topo[u] = ++cnt;
        for(int v : vec[u]) if(!(--in[v])) q.push(v);
    }
    ans.clear(); if(cnt != n) return false;
    rep(i, 1, m) if(e[i].w <= x && topo[e[i].u] > topo[e[i].v]) ans.pb(i);
    return true;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    rep(i, 1, m) { cin >> e[i].u >> e[i].v >> e[i].w, val[i] = e[i].w; }
    sort(val + 1, val + 1 + m); int t = unique(val + 1, val + 1 + m) - val - 1;
    int l = 0, r = t;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(val[mid])) r = mid; else l = mid + 1;
    }
    check(val[l]); cout << val[l] << ' ' << ans.size() << '\n';
    rep(i, 0, (int)ans.size() - 1) cout << ans[i] << " \n"[i == iEND];
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/9uq0cnla