-
分析
看到求最大值最小，不难想到二分。
很容易想到二分最大可取边长度。
思考如何check。首先如果存在一点 \(u\) 符合条件，那么我们很难判断那条边该翻哪条边不该翻，很难去check。
那么大胆假设对于每个点 \(u\)，每条边的方向只会确定为一个状态。
尝试证明。
假设存在边 \(a, b\) 不得不正反取两次。
因为这条边不得不正着取一次，所以说明 \(a\) 这一端的点无法到达 \(b\) 且能到达 \(a\)。
因为这条边不得不反着取一次，所以说明 \(b\) 这一端的点无法到达 \(a\) 且能到达 \(b\)。
若 \(a\)、\(b\) 均能到达，那么这条边的正反都没有必要经过，产生矛盾。
原命题证伪，逆命题成立。
证毕。
所以我们可以直接把正反两条边全加上去，因为最后只会取一条。思考如何检查存在合法点。
首先原图是有向图，想到缩点，于是将原图缩成DAG。
DAG中入度为 \(0\) 的点不能通过其他边到达，所以只能有一个作为起点，如果有两个及以上自然不合法。
而且DAG只要能以所有入度为 \(0\) 的点拓扑肯定能够到达所有的点。
那么显然如果只存在一个点入度为 \(0\)，那么这个点就是合法的点。缩点和检查入度的时空复杂度都是线性，计算强联通分量的入度因为需要去除重边很难做到空间线性，但是我们只需要检查入度为 \(0\) 的点，这种点不会被重边影响，重边只会使原本入度就为正数的点入度增加，所以直接不管重边直接计算强联通分量的入度即可。
最后总的时间复杂度为 \(\mathcal{O(n \log w)}\)，\(w\) 为值域 \(1e9\)，可以通过本题。
-
代码
#include <iostream>
#include <vector>
using namespace std;
constexpr int MAXN(1000007);
int dfn[MAXN], low[MAXN], st[MAXN], vis[MAXN], scc[MAXN], dfs_clock, top, scccnt;
int deg[MAXN];
int l, r, mid, ans;
int T, n, m;
struct node{ int id, w; };
vector <node> e[MAXN];
inline void read(int &temp) { cin >> temp; }
inline void tarjan(int u) {
dfn[u] = low[u] = ++dfs_clock, st[++top] = u, vis[u] = 1;
for (auto v : e[u]) {
if (v.w > mid) continue;
if (!dfn[v.id]) tarjan(v.id), low[u] = min(low[u], low[v.id]);
else if (vis[v.id]) low[u] = min(low[u], dfn[v.id]);
}
if (dfn[u] == low[u]) {
++scccnt;
int v(0);
while (1) {
v = st[top--];
vis[v] = 0, scc[v] = scccnt;
if (v == u) break;
}
}
}
inline bool check() {
for (int i(1); i <= n; ++i) dfn[i] = 0, vis[i] = 0;
for (int i(1); i <= scccnt; ++i) deg[i] = 0;
scccnt = 0, top = 0, dfs_clock = 0;
for (int i(1); i <= n; ++i) if (!dfn[i]) tarjan(i);
for (int u(1); u <= n; ++u)
for (auto v : e[u]) if (scc[u] != scc[v.id] && v.w <= mid) ++deg[scc[v.id]];
int cnt(0);
for (int i(1); i <= scccnt; ++i) cnt += !deg[i];
if (cnt > 1) return false;
return true;
}
inline void work() {
for (int i(1); i <= n; ++i) e[i].clear();
read(n), read(m);
for (int i(1), u, v, w; i <= m; ++i) read(u), read(v), read(w), e[u].push_back((node){v, 0}), e[v].push_back((node){u, w});
l = 0, r = 1000000000;
ans = -1;
while (l <= r) {
mid = (l + r) >> 1;
if (check()) r = mid - 1, ans = mid;
else l = mid + 1;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
read(T);
while (T--) work();
return 0;
}