1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<int> vi; typedef pair<int, int> pii;
#define rep(i, a, n) for (int i = a; i < n; ++i) #define per(i, a, n) for (int i = n - 1; i >= a; --i) #define fi first #define pb push_back #define mp make_pair #define EPS 1e-8 #define INF 0x3f3f3f3f3f #define endl '\n' #define all(x) x.bgein(), x.end()
const int maxn = 2e4 + 5; const int maxm = 2e5 + 5; struct Edge { int u, v, w; Edge(int _u, int _v, int _w) : u(_u) , v(_v) , w(_w) { } Edge() {} bool operator<(const Edge b) { return w > b.w; } } p[maxm];
vector<pii> e[maxn]; int n, m, k, t, vis[maxn];
inline void init() { rep(i, 0, n + 1) e[i].clear(); }
bool dfs(int x, int co) { vis[x] = co; rep(i, 0, e[x].size()) { int y = e[x][i].first; if (vis[y] == co) return 0; else if (!vis[y] && !dfs(y, 3 - co)) return 0; } return 1; }
inline bool pd(int mid) { init(); memset(vis, 0, sizeof(vis)); rep(i, 0, m) { if (p[i].w <= mid) break; e[p[i].u].pb(mp(p[i].v, p[i].w)); e[p[i].v].pb(mp(p[i].u, p[i].w)); } rep(i, 1, n + 1) { if (!vis[i] && !dfs(i, 1)) return 0; } return 1; }
int main() { ios::sync_with_stdio(false); while (cin >> n >> m) { rep(i, 0, m) { cin >> p[i].u >> p[i].v >> p[i].w; } sort(p, p + m); int l = 0, r = p[0].w, mid; while (l < r) { mid = (l + r) >> 1; if (pd(mid)) r = mid; else l = mid + 1; } cout << l << endl; } }
|