<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
染色法+二分查找
需求是最小化发生冲突影响力的最大值,很容易想到二分查找
将每一对罪犯抽象为节点,怨气值就是节点之间边的权值,然后直接从最大值limit入手,在原图中去掉权值小于limit的边,然后判断剩余边能否构成二分图,能的话就说明limit是一个可行的最大值(判断二分图的方法和细节见注释)
二分搜索时,整个搜索区段为0到$max(c)$,c为怨气值,对于最终最小化完成的最大值来说,大于它的值都可行,小于它的值都不可行,像这样的二元性是二分查找法可行的必要条件
时间复杂度
$O(n*log(max(c))$
C++ 代码
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <vector>
#include <queue>
using namespace std;
using Node = pair<int, int>;
//依旧是邻接表法
vector<vector<Node>> adjList;
vector<int> colors;
int n, m, s, e, v, mv = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
adjList.resize(n + 1);
colors.resize(n + 1);
for (int i = 0; i < m; i++) {
cin >> s >> e >> v;
adjList[s].push_back({ e,v });
adjList[e].push_back({ s,v });
mv = max(v, mv);
}
//只连上权值大于limit的边,判断此图是不是二分图,是的话,limit就是个可能的最大值
function<bool(int)> check = [=](int limit)->bool {
queue<int> q;
//染色法判断二分图,交替的为相邻节点染色
//如果遇到了相邻同色的情况,就说明这个图不是二分图
fill(colors.begin(), colors.end(), 0);
//0代表没有染色,1和-1代表两种不同颜色
for (int i = 1; i <= n; i++) {
if (colors[i] == 0) {
q.push(i);
colors[i] = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
for (auto& [nx, val] : adjList[cur]) {
if (val > limit) {
//未染色,尝试染不同颜色
if (colors[nx] == 0) {
colors[nx] = -colors[cur];
q.push(nx);
}
//已染相同颜色,返回false
if (colors[nx] == colors[cur]) return false;
}
}
}
}
}
return true;
};
//二分搜索,确定最小化的最大值
int low = 0, high = mv;
while (low < high) {
int mid = (low + high) / 2;
if (check(mid)) high = mid;
else low = mid + 1;
}
cout << low << endl;
return 0;
}