赛时：看不懂题，啊这！
赛后：就这？
题目描述
有一个简单相连的无向图，其顶点数为 \(n\)，编号为 \(1\) 至 \(n\)。图中有 \(m\) 条加权边，第 \(i\) 条边连接顶点 \(a_i\) 和 \(b_i\)，权重为 \(w_i\)。此外，连接两个顶点的简单路径的权重是简单路径中包含的边的权重之和。
我们给每个顶点涂上红色或蓝色。求满足以下条件的着色的整数 \(x\) 的最大值：对于连接涂有相同颜色的两个不同顶点的每一条简单路径，简单路径的权重至少为 \(x\)。
具体思路
显然二分查找最大的 \(x\)，考虑 check 函数怎么打。
首先，对于权值大于 \(x\) 的边，对答案不会造成任何影响，因为几条比 \(x\) 大的边怎么加也不会比 \(x\) 小。
然后，考虑权值小于 \(x\) 的边，那么它连接的两个顶点一定不能染成一种颜色。于是我们给权值小于 \(x\) 的边连接的所有点跑一遍二分图染色，能染色说明当前的 \(x\) 可行，反之不行。
但是我们直接染色是不行的，因为我们还没考虑染色后，相同颜色的点之间的距离大于等于 \(x\)。
我们只需要考虑两条边即可，因为多条边也是一样的。我们可以预处理出每个点连着边的最小边权与次小边权的和，然后取一个最小值，这样选出来的最小值就是整个图里面任意两点距离的最小值。我们把这个东西设为二分的上界，就可以保证枚举的 \(x\) 小于等于任意两条边的和，即任意相同颜色的点距离大于等于 \(x\)。
要注意一点的是，二分的 \(l\) 和 \(r\) 极限情况下是会到 \(2e9\) 的，这个时候你 \(mid=(l+r)/2\) 一加，就会爆 int，所以记得要开 long long。
设 \(w\) 为二分上界，时间复杂度：\(O(n \log w)\)。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=2e5+5;
const LL inf=0x3f3f3f3f;
struct edge{LL x,y,c,pre;}a[2*N];LL last[N],alen;
void ins(LL x,LL y,LL c){
a[++alen]=edge{x,y,c,last[x]};
last[x]=alen;
}
LL n,m,color[N];
LL minn[N],next_minn[N];
void solve(LL x,LL c){
if(c<minn[x]){
next_minn[x]=minn[x];
minn[x]=c;
}
else if(minn[x]<=c&&c<next_minn[x]){
next_minn[x]=c;
}
}
bool dfs(LL x,LL mid,LL c){
color[x]=c;
for(LL k=last[x];k;k=a[k].pre){
if(a[k].c>=mid)continue;
LL y=a[k].y;
if(color[x]==color[y])
return false;
if(!color[y]&&!dfs(y,mid,3-c))
return false;
}
return true;
}
bool check(LL mid){
memset(color,0,sizeof(color));
for(LL i=1;i<=n;i++)
if(!color[i])
if(!dfs(i,mid,1))
return false;
return true;
}
int main(){
scanf("%lld%lld",&n,&m);
alen=1;memset(last,0,sizeof(last));
memset(minn,0x3f,sizeof(minn));
memset(next_minn,0x3f,sizeof(next_minn));
for(LL i=1;i<=m;i++){
LL x,y,c;scanf("%lld%lld%lld",&x,&y,&c);
ins(x,y,c),ins(y,x,c);
solve(x,c),solve(y,c);
}
LL l=0,r=2e9,ans;
for(LL i=1;i<=n;i++){
r=min(r,minn[i]+next_minn[i]);
}
while(l<=r){
LL mid=(l+r)>>1;
if(check(mid)){
l=mid+1;
ans=mid;
}
else r=mid-1;
}
printf("%d",ans);
return 0;
}