【问题描述】
有两个监狱，要关押n个罪犯。两个罪犯直接可能会有怨气值，若这两人在同一个监狱，则会爆发一个事件，事件的影响力等于两个罪犯的怨气值。答案等于所有事件的影响力的最大值，要使答案最小。有m对罪犯有怨气值。
n≤20000，m≤100000
【分析】
曾经有大牛说过，一般题目求“最小值的最大值”或“最大值的最小值”的话，都可以用二分做。这句话真心很好用啊！
二分答案，然后构造二分图，即怨气值大于答案的罪犯需在不同监狱，若可以构造则修改右边界，否则修改左边界。总时间复杂度O(n log c)。
【代码】
PS:懒得写链表直接用vector存边不要介意。
#include#include #include #include #include using namespace std;struct edge{ int y,v; edge(const int a,const int b):y(a),v(b){}};vector e[20010];int a[20010];bool p[20010];int n,m;int Max;bool dfs(int x){ p[x] = true; for (int i = 0;i < e[x].size();i ++) { int j = e[x][i].y,v = e[x][i].v; if (v <= Max) continue; if (p[j]) { if (a[x] + a[j] != 1) { return false; } } else { a[j] = 1 - a[x]; if (!dfs(j)) return false; } } return true;}bool check(int k){ Max = k; memset(a,0,sizeof(a)); memset(p,0,sizeof(p)); for (int i = 1;i <= n;i ++) if (!p[i]) if (!dfs(i)) return false; return true;}int main(){ freopen("prison.in","r",stdin); freopen("prison.out","w",stdout); scanf("%d %d",&n,&m); for (int i = 1;i <= m;i ++) { int x,y,v; scanf("%d %d %d",&x,&y,&v); e[x].push_back(edge(y,v)); e[y].push_back(edge(x,v)); } int l = 1,r = 0x3f3f3f3f; while (r > l ) { int mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; } cout << l; fclose(stdin);fclose(stdout);}