给定一张 \(n\) 个点 \(m\) 条边的边带权简单连通无向图。现需要将其的每个结点染成黑色或白色。
定义两个结点的距离为这两点间所有路径的边权之和的最小值。
对于一种染色的方式，定义一个结点 \(u\) 的代价为：对于所有与 \(u\) 异色的点 \(v\)，\(u\) 和 \(v\) 的距离的最小值。如果不存在这样的点，那么代价为 \(10^{100}\)。
该染色方式的代价为所有结点的代价的最大值。
您需要构造一种染色方式，使其最小化代价。
\(2\le n \le 5\times 10^5\)，图简单连通。
注意到有一档子任务，\(m=n-1\)，是一颗树状图的情况。我们注意到这是只能一层染一个颜色，此时答案为 \(\max_{i=1}^{m} val_i\)。所以我们在普通情况则是先拿出一个最小生成树，答案就是最小生成树中的最大值。时间复杂度 \(O(m\log m)\)。
点击查看代码
int n,m;
struct edge {int u,v,d; };
vector<int>G[maxn];
edge x[maxn];
bool vis[maxn],ans[maxn];
bool cmp(edge x,edge y) {
return x.d<y.d;
}
mt19937 rd(time(NULL));
void dfs2(int x) {
queue<int> q1,q2;
q1.push(x),q2.push(0);
vis[x]=1;
while(!q1.empty()) {
int u=q1.front(),val=q2.front();
q1.pop(),q2.pop();
ans[u]=val;
for(auto v:G[u]) {
if(!vis[v]) {
vis[v]=1;
q1.push(v),q2.push((val^1));
}
}
}
}
int fa[maxn];
int find(int x) {return x==fa[x]?x:(fa[x]=find(fa[x])); }
signed main() {
in2(n,m);
For(i,1,m) {
int u,v,d;
in3(u,v,d);
x[i]={u,v,d};
}
sort(x+1,x+m+1,cmp);
For(i,1,n) fa[i]=i;
For(i,1,m) {
auto [u,v,d]=x[i];
if(find(u)!=find(v)) {
// cout<<u<<' '<<v<<'\n';
fa[find(u)]=find(v);
pb(G[u],v);
pb(G[v],u);
}
}
dfs2(1);
For(i,1,n) cout<<ans[i];
return 0;
}