算法
(二分，染色法判断二分图) O((N+M)logC)
将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。
那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。
我们在 [0,109] 之间枚举最大边权 limit，当 limit 固定之后，剩下的问题就是：
- 判断能否将所有点分成两组，使得所有权值大于 limit 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 limit 的边构成的新图是否是二分图。
判断二分图可以用染色法，时间复杂度是 O(N+M)，其中 N 是点数，M 是边数，可以参考AcWing 860. 染色法判定二分图。
为了加速算法，我们来考虑是否可以用二分枚举 limit， 假定最终最大边权的最小值是 Ans:
- 那么当 limit∈[ans,109] 时，所有边权大于 limit 的边，必然是所有边权大于 Ans 的边的子集，因此由此构成的新图也是二分图。
- 当 limit∈[0,ans−1] 时，由于 ans 是新图可以构成二分图的最小值，因此由大于 limit 的边构成的新图一定不是二分图。
- 所以整个区间具有二段性，可以二分出分界点 ans 的值。二分算法模板可以参考这篇。
时间复杂度分析
总共二分 logC 次，其中 C 是边权的最大值，每次二分使用染色法判断二分图，时间复杂度是 O(N+M)，其中 N 是点数，M 是边数。因此总时间复杂度是 O((N+M)logC)。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20010, M = 200010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
bool dfs(int u, int c, int limit)
{
color[u] = c;
for (int i = h[u]; ~i; i = ne[i])
{
if (w[i] <= limit) continue;
int j = e[i];
if (color[j])
{
if (color[j] == c) return false;
}
else if (!dfs(j, 3 - c, limit)) return false;
}
return true;
}
bool check(int limit)
{
memset(color, 0, sizeof color);
for (int i = 1; i <= n; i ++ )
if (color[i] == 0)
if (!dfs(i, 1, limit))
return false;
return true;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
int l = 0, r = 1e9;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
return 0;
}
贴一个用并查集的，时间复杂度O(mlogm)
#include<iostream> #include<algorithm> using namespace std; const int N = 20100, M = 100010; int p[N], d[N]; struct Edge { int a, b, c; bool operator<(const Edge e) const { return c > e.c; } }edge[M]; int find(int x) { if (x != p[x]) { int t = p[x]; p[x] = find(p[x]); d[x] += d[t]; } return p[x]; } int main() { int n, m; cin >> n >> m; int a, b, c; for (int i = 0; i < m; ++ i) { scanf("%d%d%d", &a, &b, &c); edge[i] = {a, b, c}; } sort(edge, edge + m); for (int i = 1; i <= n; ++ i) p[i] = i; bool flag = true; for (int i = 0; i < m; ++ i) { int a = edge[i].a, b = edge[i].b, c = edge[i].c; int pa = find(a), pb = find(b); if (pa == pb) { if ((d[a] - d[b] - 1) % 2 != 0) { cout << c << endl; flag = false; break; } } else { p[pa] = pb; d[pa] = d[b] - d[a] + 1; } } if (flag) cout << 0 << endl; return 0; }tql
重载运算符这里和快排用的很妙
这里为什么还要sort啊？感觉没什么影响啊？
y总太强了，学了半年就已经可以写出这个题了，我学了一年还是什么都不会
啊？真的吗，y总在哪说的呀请问
# Y总太强了
代码完全y风hh
## ○|￣|_
是
colour不是color，世界是用的英式英语纠结这个不如多刷两个题
XD
小tips：
最大值最小或者最小值最大这种问题常常会用到二分答案，然后每次check一下，而且这种题都有一个特点，你会发现正向去做做不了（当然可能是我太菜了qwq）
这里二分图染色的应用太强了吧
○|￣|_
#include<iostream> #include<algorithm> #include<vector> #include<cstring> const int Max=1e5+1; using namespace std; int hatred[Max]; int color[Max]; struct ele{ int to,weight; ele(int a,int b){ to=a,weight=b; } }; vector<ele> v[Max]; void add(int a,int b,int c){ ele tmp(b,c); v[a].push_back(tmp); } int Mid; void print(int n){ for(int i=1;i<=n;i++){ cout<<color[i]<<" "; } cout<<endl; } bool dfs(int n,int c){ //print(4); color[n]=c; //print(4); for(auto it=v[n].begin();it!=v[n].end();it++){ if((*it).weight>hatred[Mid]){ // cout<<n<<(*it).to<<endl; if(color[(*it).to]==0){ dfs((*it).to,3-c); }else{ if(color[(*it).to]==c){ return false; } } } } return true; } int main(){ int n,m; cin>>n>>m; int a,b,c; for(int i=1;i<=m;i++){ cin>>a>>b>>c; add(a,b,c); add(b,a,c); hatred[i]=c; } sort(hatred,hatred+1+m); int l=0,r=m; while(l!=r){ Mid=(l+r)/2; // cout<<l<<" "<<r<<" "<<hatred[Mid]<<endl; memset(color,0,sizeof(color)); bool flag=false; for(int i=1;i<=n;i++){ if(color[i]==0){ //cout<<114; if(!dfs(i,1)){ flag=true; break; } } } //print(n); if(!flag){ r=Mid; }else{ l=Mid+1; } //cout<<l<<" "<<r<<endl; } Mid=(l+r)/2; cout<<hatred[Mid]; }/* 2 1 1 2 28135 */y总请问我这个做法问题在哪呢？谢谢
你的dfs函数的第一个if那里，应该写成 if(color[(it).to]==0){ if(!dfs((it).to,3-c)) return false};
谢谢！
说一下if (w[i] < limit) continue；和if (w[i] <= limit) continue；这两种情况，前者二分的是二分图两个集合之间的边，后者二分的是二分图内部的边，前者二分出来的正好是答案，后者二分出来的应该正好大于答案，所以减一之后就是答案
是不是说反了，还是说我理解错了= =
不好意思是说反了
前者减一是答案，后者是答案
这些题到底是无向图还是有向图
为啥改为if (w[i] < limit) continue;就错了捏
就是为啥在二分的时候所有大于mid的可以分到二分图中，而所有大于等于mid的分到二分图中就是错的？
因为limit这条边要在两组其中的一组内
因为mid是符合条件的最大值，也就是要在一个集合中
%%%
我龙傲天佩服！
%%%
这就是京东笔试题
太强啦，y总！
没想到这道题是这样做的。
蒟蒻求助……
#include<bits/stdc++.h> //#pragma GCC optimize(2) using namespace std; const int N=20005,M=200005; int n,m,tot,r=1e9,l; int e[M],h[N],ne[M],w[M]; int v[N]; void add(int x,int y,int z){ e[tot]=y,w[tot]=z,ne[tot]=h[x],h[x]=tot++; } bool dfs(int x,int col,int mid){ v[x]=col; for(int i=h[x];i;i=ne[i]){ if(w[i]<=mid) continue; int y=e[i]; if(v[y]==0){ if(!dfs(y,3-i,mid)) return false; } else if(v[y]==col) return false; } return true; } bool chk(int mid){ memset(v,0,sizeof(v)); for(int i=1;i<=n;i++) if(v[i]==0) if(!dfs(i,1,mid)) return false; return true; } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c);add(b,a,c); } while(r>l){ int mid=(l+r)>>1; if(chk(mid)) r=mid; else l=mid+1; } printf("%d",l); return 0; }判断那边应该是
3-col把#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 20010, M = 200010; int n, m; int h[N], e[M], w[M], ne[M], idx; int color[N]; void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ; } bool dfs(int u, int c, int limit) { color[u] = c; for (int i = h[u]; ~i; i = ne[i]) { if (w[i] <= limit) continue; int j = e[i]; if (color[j]) { if (color[j] == c) return false; } else if (!dfs(j, 3 - c, limit)) return false; } return true; } bool check(int limit) { memset(color, 0, sizeof color); for (int i = 1; i <= n; i ++ ) if (color[i] == 0) if (!dfs(i, 1, limit)) return false; return true; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); while (m -- ) { int a, b, c; scanf("%d%d%d", &a, &b, &c); add(a, b, c); add(b, a, c); } int l = 0, r = 1e9; while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } printf("%d\n", l); return 0; }