<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/P2916" target="_blank" rel="noreferrer noopener">P2916 [USACO08NOV] Cheering up the Cow G</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>板子题，考虑每条边的贡献，由于每条边必然会被经过两次，则对于这条边的花费就为 $2w_i+cost_u+cost_v$，将边权替换为此花费，跑一遍Kruskal即可。最后还要加上起点的花费，因为是任意起点，选花费最小的作为起点就行了。</p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=10005;
int n,m;
ll c[maxn];
ll sum;
struct edge{
ll u,v,w;
}e[maxn*10];
int f[maxn];
int dsu_find(int x){
return x==f[x]?x:f[x]=dsu_find(f[x]);
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
void kruskal(){
for(int i=1;i<=n;i++)f[i]=i;
sort(e+1,e+1+m,cmp);
int cnt=0;
for(int i=1;i<=m;i++){
int u=dsu_find(e[i].u),v=dsu_find(e[i].v);
if(f[u]==f[v])continue;
f[u]=v;
sum+=e[i].w;
//cout<<e[i].u<<" "<<e[i].v<<endl;
if(++cnt==n-1)break;
}
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;
ll mi=0x3f3f3f3f;
for(int i=1;i<=n;i++)cin>>c[i],mi=min(mi,c[i]);
for(int i=1;i<=m;i++){
int x;
cin>>e[i].u>>e[i].v>>x;
e[i].w=2*x+c[e[i].u]+c[e[i].v];
}
kruskal();
cout<<(sum+mi)<<endl;
return 0;}</code></pre>
</details>
<!-- /wp:html -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/P1967" target="_blank" rel="noreferrer noopener">P1967 [NOIP2013 提高组] 货车运输</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>题目实际是要使得图中两点间路径中的边权最小值尽可能大，考虑用Kruskal求一个最大生成树，此时图中的边权都尽可能大了。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>由于司机要从一地到另一地，可以用LCA处理两点间路径，再用LCA预处理时顺带预处理出LCA路径上的边权最小值即可，但要注意的是图不一定连通，可能有多个连通块，要从每一个根节点开始预处理。</p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
const int maxn1=50005,maxn2=10005;
const int INF=0x3f3f3f3f;
int log2n;
int n,m,f[maxn2];
int de[maxn2],fa[maxn2][22],dp[maxn2][22];
struct edge{
int u,v,z;
}e[maxn1];
struct edge2{
int to;
int v;
};
vector<edge2> g[maxn2];
bool cmp(edge x,edge y){
return x.z>y.z;
}
int dsu_find(int x){
return f[x]==x ? x : f[x]=dsu_find(f[x]);
}
bool kruskal(){
sort(e+1,e+1+m,cmp);
for(int i=1;i<=n;i++)f[i]=i;
int s=0,cnt=0;
for(int i=1;i<=m;i++){
int fu=dsu_find(e[i].u);
int fv=dsu_find(e[i].v);
if(fu==fv)continue;
f[fu]=fv;
edge2 u={e[i].v,e[i].z};
g[e[i].u].push_back(u);
u={e[i].u,e[i].z};
g[e[i].v].push_back(u);
if(++cnt==n-1)break;
}
}
void dfs(int x,int fath) {
for(int i=1;i<log2n;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
dp[x][i]=min(dp[x][i-1],dp[fa[x][i-1]][i-1]);
}
for(int i=0;i<g[x].size();i++){
int to=g[x][i].to;
if(to==fath)continue;
fa[to][0]=x;
dp[to][0]=g[x][i].v;
de[to]=de[x]+1;
dfs(to,x);
}}
int lca(int x,int y){
int ans=INF;
if(de[x]<de[y])swap(x,y);
for(int i=log2n;~i;i--){
if(de[fa[x][i]]>=de[y] and fa[x][i]){
ans=min(ans,dp[x][i]);
x=fa[x][i];
}
}
if(x==y)return ans;
for(int i=log2n;~i;i--){
if(fa[x][i]!=fa[y][i]){
ans=min(ans,min(dp[x][i],dp[y][i]));
x=fa[x][i];
y=fa[y][i];
}
}
ans=min(ans,min(dp[x][0],dp[y][0]));
return ans;}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].z;
}
kruskal();
log2n=log(n)/log(2)+1;
for(int i=1;i<=n;i++){
if(dsu_find(f[i])==i){
dfs(i,0);
}
}
int q;
cin>>q;
for(int i=1;i<=q;i++){
int x,y;
cin>>x>>y;
if(dsu_find(f[x])!=dsu_find(f[y])){
cout<<-1<<endl;
}
else{
cout<<lca(x,y)<<endl;
}
}
return 0;}</code></pre>
</details>
<!-- /wp:html -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/P2323" target="_blank" rel="noreferrer noopener">P2323 [HNOI2006] 公路修建问题</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>题目中说必须要修够k条一级公路，使得花费最多的一条公路的花费尽可能少，因此显然可以知道，这k条一级公路必须要修，并且花费尽可能小，只要用Kruskal对一级公路求一个最小生成树，按顺序取其中k条边，并记录边及边权最大值。剩下的用同样方法对二级公路用Kruskal加边，更新最大值即可。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>一个惨痛的教训：在一个图里多次跑Kruskal的时候，千万不要每跑一次前就初始化一次并查集，一开始初始化一遍就够了！！！</p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
const int maxn=20005;
int n,m,k,f[maxn],bj[maxn];
int s=0,tot=0;
struct edge{
int t,u,v,c1,c2;
}e[maxn];
struct node{
int bh,gl;
}ans[maxn];
int dsu_find(int x){
return f[x]==x ? x : f[x]=dsu_find(f[x]);
}
bool cmp1(edge x,edge y){
return x.c1<y.c1;
}
bool cmp2(edge x,edge y){
return x.c2<y.c2;
}
bool cmp3(node x,node y){
return x.bh<y.bh;
}
void kruskal1(){
int cnt=0;
for(int i=1;i<m;i++){
int fu=dsu_find(e[i].u),fv=dsu_find(e[i].v);
if(fu==fv or bj[e[i].t])continue;
f[fv]=fu;
bj[e[i].t]=1;
ans[++tot].bh=e[i].t;
ans[tot].gl=1;
s=max(s,e[i].c1);
if(++cnt==k)break;
}}
void kruskal2(){
int cnt=0;
for(int i=1;i<m;i++){
int fu=dsu_find(e[i].u),fv=dsu_find(e[i].v);
if(fu==fv or bj[e[i].t])continue;
f[fv]=fu;
bj[e[i].t]=1;
ans[++tot].bh=e[i].t;
ans[tot].gl=2;
s=max(s,e[i].c2);
if(++cnt==n-1-k)break;
}}
int main(){
ios::sync_with_stdio(0);
cin>>n>>k>>m;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<m;i++){
cin>>e[i].u>>e[i].v>>e[i].c1>>e[i].c2;
e[i].t=i;
}
sort(e+1,e+m,cmp1);
kruskal1();
sort(e+1,e+m,cmp2);
kruskal2();
sort(ans+1,ans+n,cmp3);
cout<<s<<endl;
for(int i=1;i<n;i++){
cout<<ans[i].bh<<" "<<ans[i].gl<<endl;
}
return 0;}</code></pre>
</details>
<!-- /wp:html -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/P3623" target="_blank" rel="noreferrer noopener">P3623 [APIO2008] 免费道路</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>题目大意其实就是有边权为0和1的边，求边权总和为k的生成树。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>考虑先从0边开始跑一遍Kruskal，如果此时图没有连通，说明此时还需加入一些1边才能使图连通，而这些1边就是生成树必须要有的边，由此确定了一部分1边。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>由于已经确定了一部分1边，生成树也可以基本确定，此时第二遍从1边开始跑Kruskal（跑之前要先将已确定的1边加入），选够k条1边后再选0边，即可求出生成树。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>无解情况：</p>
<!-- /wp:paragraph -->
<!-- wp:list -->
<ul><li>选的1边数大于或小于k</li><li>图不连通</li></ul>
<!-- /wp:list -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
int n,m,k;
int f[20005];
struct edge{
int u,v,w,bj=0;
}e[maxn];
int dsu_find(int x){
return f[x]==x ? x : f[x]=dsu_find(f[x]);
}
bool cmp1(edge x,edge y){
return x.w<y.w;
}
bool cmp2(edge x,edge y){
if(x.w==y.w)return x.bj>y.bj;
return x.w>y.w;
}
void kruskal1(){
int cnt=0;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
int fu=dsu_find(e[i].u),fv=dsu_find(e[i].v);
if(fu==fv)continue;
f[fv]=fu;
if(e[i].w==1)e[i].bj=1;
if(++cnt==n-1)break;
}
}
void kruskal2(){
int cnt=0,kk=k;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
if(e[i].bj){
f[dsu_find(e[i].v)]=dsu_find(e[i].u);
cnt++;
kk--;
continue;
}
int fu=dsu_find(e[i].u),fv=dsu_find(e[i].v);
if(fu==fv)continue;
f[fv]=fu;
e[i].bj=1;
if(e[i].w)kk--;
if(!kk)for(;e[i].w;i++);
if(++cnt==n-1)break;
}
if(kk>0){
cout<<"no solution"<<endl;
exit(0);
}}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int ww;
cin>>e[i].u>>e[i].v>>ww;
e[i].w=1-ww;
}
sort(e+1,e+1+m,cmp1);
kruskal1();
sort(e+1,e+1+m,cmp2);
kruskal2();
for(int i=1;i<=m;i++){
if(e[i].bj){
cout<<e[i].u<<" "<<e[i].v<<" "<<(1-e[i].w)<<endl;
}
}
return 0;}</code></pre>
</details>
<!-- /wp:html -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/P1550" target="_blank" rel="noreferrer noopener">P1550 [USACO08OCT] Watering Hole G</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>稍微抽象一下题意，无向图有一堆带权值的边和点，当选定了一个点时，与它连通的点就不用计它的权值，不难看出，可以将点权转化为边权，也就是建立一个超级源点，与其他每个点都有连边，该边的边权就是连向的点的点权，这样就能把所有权值都统一为边权。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>题目要求使得图连通的最少钱数，跑个Kruskal即可。</p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=305;
int n,m,tot;
int c[maxn],f[maxn];
ll sum;
struct edge{
int u,v,w;
}e[maxn*maxn];
int dsu_find(int x){
return x==f[x]?x:f[x]=dsu_find(f[x]);
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
void kruskal(){
for(int i=0;i<=n;i++)f[i]=i;
sort(e+1,e+1+tot,cmp);
int cnt=0;
for(int i=1;i<=tot;i++){
int fu=dsu_find(e[i].u),fv=dsu_find(e[i].v);
if(fu==fv)continue;
f[fu]=fv;
sum+=e[i].w;
if(++cnt==n)break;
}
}
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++){
int x;
cin>>x;
e[++tot]={0,i,x};
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
cin>>x;
if(i<j){
e[++tot].u=i;
e[tot].v=j;
e[tot].w=x;
}
}
}
kruskal();
cout<<sum<<endl;
return 0;}</code></pre>
</details>
<!-- /wp:html -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/P5994" target="blank" rel="noreferrer noopener">P5994 [PA2014] Kuglarz</a></h3>
<!-- /wp:heading -->
<!-- wp:list -->
<ul><li>题目要求每个杯子底下是否藏有球，其实就是想知道每个杯子的奇偶性</li></ul>
<!-- /wp:list -->
<!-- wp:paragraph -->
<p>定义 $F(l,r)$ 表示 $[l,r]$ 区间球的总数。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>而如果我们想知道 $F(l,l)$ 的奇偶性，那么只需要知道 $F(l+1,r)$ 和 $F(l,r)$ 的奇偶性或者直接花费 $c{l,l}$ 查询该点，对于 $F(r,r)$ 同理。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>考虑把 $F(l,r)$ 看作点 $l-1$ 向点 $r$ 连了一条边，$F(l,l)$ 就相当于点 $l-1$ 向点 $l$ 连了一条边。当所有点都连通时，那就必然可以从相邻点推出这两点间边的奇偶性，也就是知道了 $F(l,l)$ 的奇偶性。要使花费最小，跑个Kruskal即可。</p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2005;
int n,tot;
ll sum;
int f[maxn];
struct edge{
int u,v,w;
}e[maxn*maxn];
int dsu_find(int x){
return x==f[x]?x:f[x]=dsu_find(f[x]);
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
void kruskal(){
for(int i=0;i<=n;i++)f[i]=i;
sort(e+1,e+tot+1,cmp);
int cnt=0;
for(int i=1;i<=tot;i++){
int fu=dsu_find(e[i].u),fv=dsu_find(e[i].v);
if(fu==fv)continue;
f[fu]=fv;
sum+=e[i].w;
if(++cnt==n)break;
}
}
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
cin>>e[++tot].w;
e[tot].u=i-1;
e[tot].v=j;
}
}
kruskal();
cout<<sum<<endl;
return 0;}</code></pre>
</details>
<!-- /wp:html -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/CF1687B" target="_blank" rel="noreferrer noopener">CF1687B Railway System</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>这题写了篇题解，详见<a href="https://www.luogu.com.cn/blog/xgnd/solution-cf1687b">这里</a>。</p>
<!-- /wp:paragraph -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/CF609E" target="_blank" rel="noreferrer noopener">CF609E Minimum spanning tree for each edge</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>非严格次小生成树板子题。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>Kruskal求出最小生成树后，先倍增预处理出树上两点的最近公共祖先和路径上边权最大值。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>$1$ 到 $m$ 枚举每条边，若该边在最小生成树里，直接输出其权值和；若不在，考虑将路径权值最大的边删去，再加入这条边时，边权和最小，边权和为 $sum+w<em>k-max</em>{i,j}$ 。（ $sum$ 为最小生成树边权和，$w<em>k$ 为此边边权，$max</em>{i,j}$ 为树上两点 $i$，$j$ 路径上边权最大值）</p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=200005;
int n,m;
ll sum;
int f[maxn];
int mx[maxn][22];
int fa[maxn][22];
int dep[maxn];
struct edge{
int u,v,w,p;
bool bj;
}e[maxn];
struct edge1{
int to,v;
};
vector<edge1>g[maxn];
int dsu_find(int x){
return x==f[x]?x:f[x]=dsu_find(f[x]);
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
bool cmp_num(edge x,edge y){
return x.p<y.p;
}
void kruskal(){
for(int i=1;i<=n;i++)f[i]=i;
sort(e+1,e+1+m,cmp);
int cnt=0;
for(int i=1;i<=m;i++){
int fu=dsu_find(e[i].u),fv=dsu_find(e[i].v);
if(fu==fv)continue;
f[fu]=fv;
sum+=e[i].w;
e[i].bj=1;
g[e[i].u].push_back({e[i].v,e[i].w});
g[e[i].v].push_back({e[i].u,e[i].w});
if(++cnt==n-1)break;
}
}
void dfs(int x,int fath,int v){
fa[x][0]=fath;
mx[x][0]=v;
dep[x]=dep[fath]+1;
for(int i=1;i<=20;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
mx[x][i]=max(mx[x][i-1],mx[fa[x][i-1]][i-1]);
}
for(int i=0;i<g[x].size();i++){
int to=g[x][i].to;
if(to==fath)continue;
dfs(to,x,g[x][i].v);
}}
int query(int x,int y){
if(dep[x]<dep[y])swap(x,y);
int ans=0;
for(int i=20;i>=0;i--){
if(dep[fa[x][i]]>=dep[y]){
ans=max(ans,mx[x][i]);
x=fa[x][i];
}
}
if(x==y)return ans;
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
ans=max(ans,max(mx[x][i],mx[y][i]));
x=fa[x][i],y=fa[y][i];
}
}
ans=max(ans,max(mx[x][0],mx[y][0]));
return ans;}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
e[i].p=i;
}
kruskal();
dfs(1,0,0);
sort(e+1,e+1+m,cmp_num);
for(int i=1;i<=m;i++){
if(e[i].bj)cout<<sum<<endl;
else {
int t=query(e[i].u,e[i].v);
cout<<(sum+e[i].w-t)<<endl;
}
}
return 0;}</code></pre>
</details>
<!-- /wp:html -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/P4180" target="_blank" rel="noreferrer noopener">P4180 [BJWC2010] 严格次小生成树</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>严格次小生成树板子题。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>与非严格次小生成树类似，考虑用非树边去替代原最小生成树的边，但可能边权最大值与新加的边的边权相等，因此要用次大值代替，若次大值也相等，就换下一条边再试。倍增预处理时再维护树上两点路径上边权次大值即可。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>注意会有重边，可以初始化答案为 $-inf$ 避免重边。</p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=300005;
const int inf=0x3f3f3f3f;
int n,m;
ll sum;
int f[maxn];
int mx[maxn][22],cmx[maxn][22];
int fa[maxn][22];
int dep[maxn];
struct edge{
int u,v,w;
bool bj;
}e[maxn];
struct edge1{
int to,v;
};
vector<edge1>g[maxn];
int dsu_find(int x){
return x==f[x]?x:f[x]=dsu_find(f[x]);
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
void kruskal(){
for(int i=1;i<=n;i++)f[i]=i;
sort(e+1,e+1+m,cmp);
int cnt=0;
for(int i=1;i<=m;i++){
int fu=dsu_find(e[i].u),fv=dsu_find(e[i].v);
if(fu==fv)continue;
f[fu]=fv;
sum+=e[i].w;
e[i].bj=1;
g[e[i].u].push_back({e[i].v,e[i].w});
g[e[i].v].push_back({e[i].u,e[i].w});
if(++cnt==n-1)break;
}
}
void dfs(int x,int fath){
fa[x][0]=fath;
dep[x]=dep[fath]+1;
for(int i=1;i<=21;i++){
fa[x][i]=fa[fa[x][i-1]][i-1];
mx[x][i]=max(mx[x][i-1],mx[fa[x][i-1]][i-1]);
cmx[x][i]=max(cmx[x][i-1],cmx[fa[x][i-1]][i-1]);
if(mx[x][i-1]>mx[fa[x][i-1]][i-1])cmx[x][i]=max(cmx[x][i],mx[fa[x][i-1]][i-1]);
else if(mx[x][i-1]<mx[fa[x][i-1]][i-1])cmx[x][i]=max(cmx[x][i],mx[x][i-1]);
}
for(int i=0;i<g[x].size();i++){
int to=g[x][i].to;
if(to==fath)continue;
mx[to][0]=g[x][i].v;
dfs(to,x);
}}
int lca(int x,int y) {
if(dep[x]<dep[y]) swap(x,y);
for(int i=20; ~i; i--) {
if(dep[fa[x][i]]>=dep[y]) {
x=fa[x][i];
}
if(x==y) return x;
}
for(int i=20; ~i; i--) {
if(fa[x][i]!=fa[y][i]) {
x=fa[x][i];
y=fa[y][i];
}
}
return fa[x][0];
}
int findmax(int x,int lca,int val){
int ans=-inf;
for(int i=20;i>=0;i--){
if(dep[fa[x][i]]>=dep[lca]){
if(mx[x][i]==val)ans=max(ans,cmx[x][i]);
else ans=max(ans,mx[x][i]);
x=fa[x][i];
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>e[i].u>>e[i].v>>e[i].w;
}
kruskal();
dfs(1,0);
ll ans=0x3f3f3f3f3f3f;
for(int i=1;i<=m;i++){
if(e[i].bj)continue;
int l=lca(e[i].u,e[i].v);
int mu=findmax(e[i].u,l,e[i].w),mv=findmax(e[i].v,l,e[i].w);
if(max(mu,mv)!=e[i].w or max(mu,mv)>-inf)ans=min(ans,(ll)sum-max(mu,mv)+e[i].w);
}
cout<<ans<<endl;
return 0;}</code></pre>
</details>
<!-- /wp:html -->
<!-- wp:heading {"level":3} -->
<h3><a href="https://www.luogu.com.cn/problem/CF1305G">CF1305G Kuroni and Antihype</a></h3>
<!-- /wp:heading -->
<!-- wp:paragraph -->
<p>update 2023.7.16</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>先考虑建出一张图，一对朋友 $(u,v)$ 对应图上一对边 $u \rightarrow v$ 边权为 $a_v$ 和 $v\rightarrow u$ 边权为 $a_u$ ，发现图可能有多个连通块，于是顺手建一个超级源点，题目就转化为求最大外向树。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>直接求最大外向树肯定不好做，但发现似乎正反边比较对称，可以考虑转化，将边权设为 $a_u+a_v$ ，那么最终答案就为最大生成树权值和减去 $\sum a_i$ ，这就很好做了。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>如果直接建图连边，边数为 $O(n^2)$ 级别，这不好。考虑来点优化，若能模拟 Kruskal 求最大生成树的过程，就不用建边了，这是好的。所以可以从大到小枚举边权 $s$ 依次加入，但对于一条边怎么知道它连的是哪个点呢？注意到有一个条件，满足 $a_u \& a<em>v=0$ 的点才连边，那么加法就相当于或，所以可以枚举 $s$ 的子集 $x$ ，找点权为 $x$ 和 $x\; XOR\; s$ 的点用并查集连起来即可。点权相同的点可以缩点当作一个点处理，一条边产生的贡献就是 $s\times (cnt</em>{a<em>u}+cnt</em>{av}-1)$。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>枚举子集复杂度为 $O(3^{log\;n})\approx O(3^{18})$ ，总复杂度为 $O(3^{18}\times\alpha(n))$。</p>
<!-- /wp:paragraph -->
<!-- wp:paragraph -->
<p>个人认为这是道好题，学到了一些套路，像转化边权、快速枚举子集、缩点之类的，感觉都比较有用。</p>
<!-- /wp:paragraph -->
<!-- wp:html -->
<details>
<summary>Code</summary>
<pre class="wp-block-code"><code>#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=400005,INF=0x3f3f3f3f;
int ;
int t,n,mx;
int cnt[maxn],fa[maxn];
ll ans;
int getfa(int x){
return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
void dsu_merge(int x,int y,ll w){
x=getfa(x),y=getfa(y);
if(x==y)return;
fa[x]=y;
ans+=1ll(cnt[x]+cnt[y]-1)w;
cnt[y]=1;
}
int main(){
ios::sync_with_stdio(0);
int n;
cin>>n;
cnt[0]=1;
for(int i=1;i<=n;i++){
int w;
cin>>w;
ans-=w;
cnt[w]++;
mx=max(mx,w);
}
int mxn=1<<32-__builtin_clz(mx);
for(int i=0;i<=mxn;i++)fa[i]=i;
for(int i=mxn;i>=0;i--){
for(int j=i;j;j=(j-1)&i){
if(cnt[j] and cnt[j^i]){
dsu_merge(j,i^j,i);
}
}
if(cnt[0] and cnt[i])dsu_merge(0,i,i);
}
cout<<ans<<endl;
return 0;}
</code></pre>
</details>
<!-- /wp:html -->
sto xgnd Orz
sto escapist404 Orz