题目
1.最大的最小，最小的最大-》二分
2.二分答案，check
3.并差集，是否在一个联通块中
#include<iostream>
#include<algorithm>
#include<numeric>//accumulate(be,en,0)
#include<cstring>//find("string"),rfind("string"),s.find(string,begin)!=s.npos
#include<string>//to_string(value)
#include<cstdio>
#include<cmath>
#include<vector>//res.erase(unique(res.begin(), res.end()), res.end()),reverse(q.begin(),q.end());
#include<queue>//priority_queue(big) /priority_queue<int, vector<int>, greater<int>> q(small)
#include<stack>
#include<map>//unordered_map
#include<set>//iterator,insert(),erase(),lower(>=)/upper_bound(>)(value)/find()return end()
#define ll long long
#define PII pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f, N = 1e5 + 5;
int n, m, k;
struct nod
{int u, v, w;
};
struct nod p[N];
bool cmp(nod k1, nod k2)
{return k1.w < k2.w;
}
vector<int>q[N];
int d[N];
int find(int x)
{if (d[x] != x) return d[x] = find(d[x]);return x;
}
bool check(int x)
{for (int i = 1; i <= n; i++) d[i] = i;int l = -1, r = m-1;while (l < r){int mid = (l + r + 1) >> 1;if (p[mid].w > x) r = mid - 1;else l = mid;}for (int i = 0; i <= l; i++) {d[find(p[i].u)] = find(p[i].v);}for (int i = 0; i < k; i++) {for (int j = 1; j < q[i].size(); j++) {if (find(q[i][j]) != find(q[i][0])) return false;}}return true;
}
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) d[i] = i;for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;p[i] = { u,v,w };}sort(p, p + m, cmp);cin >> k;for (int i = 0; i < k; i++){int s;cin >> s;for (int j = 0; j < s; j++) {int tmp;cin >> tmp;q[i].push_back(tmp);}}int l = 0, r = 1e9;while (l < r){int mid = (l + r) >> 1;if (check(mid)) r = mid;else l = mid + 1;}cout << l;
}二分两个模板
while(l<r){int mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;return l;//最后返回的l'到r都满足check}//分成[l,mid]和[mid+1,r]//check是[mid+1,r]的性质while(l<r){int mid=l+r+1>>1;if(check(mid)) r=mid-1;else l=mid;return l;//最后返回的l到l'都不满足check}//分成[l,mid-1]和[mid,r]//check是[mid,r]的性质 
