正題
題目連結:https://www.luogu.com.cn/problem/P3639
題目大意
給出\(n\)個點\(m\)條有邊權的無向圖，然後再給出\(k\)條邊權未定義的邊，然後每個點有一個人數\(p_i\)。
現在要你給未确定的邊權的邊确定邊權然後選出圖的一棵最小生成樹，之後所有點上的人都從自己的點走到根節點，當一個人經過剛剛确定邊權的邊時會支付這條邊的權值的費用，現在要求總費用和最大。
保證\(m\)條邊的圖聯通且權值互不相同。
\(1\leq n\leq 10^5,1\leq m\leq 3\times 10^5,1\leq k\leq 20\)
解題思路
突破口肯定在于權值互不相同，因為這樣的話最小生成樹就唯一了，然後發現我們加上\(k\)條邊後最多替換掉原來圖上的\(k\)條邊，是以大部分的邊都是和原來的相同的。
我們可以先把這\(k\)條邊連接配接上，然後跑一棵最小生成樹，再吧這\(k\)條邊去掉這樣就最多會産生\(k+1\)個連通塊。
然後再用聯通塊跑一次最小生成樹，把這些邊記下來，這些邊是可能使用上的。
之後我們\(2^k\)枚舉哪些邊選不選入最小生成樹上，然後拿上面的邊跑最小生成樹，之後每條邊的權值就是所有連接配接分割的兩個聯通塊的最小邊權，這個我們可以枚舉邊然後直接暴力跳，之後統計答案就好了。
時間複雜度：\(O(m\log m+2^kk^2)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const ll N=3e5+10,K=22;
struct edge{
ll x,y,w;
}e[N];
ll n,m,k,cnt,answer,p[N],fa[N],fb[N],rev[N];
ll r[K],w[K],dep[K],f[K],dx[K],dy[K],mn[K];
vector<int>G[K];ll a[K][K];
bool cmp(edge x,edge y)
{return x.w<y.w;}
ll find(ll x)
{return (fa[x]==x)?x:(fa[x]=find(fa[x]));}
ll finb(ll x)
{return (fb[x]==x)?x:(fb[x]=finb(fb[x]));}
void dfs(ll x,ll fa){
r[x]=w[x];f[x]=fa;dep[x]=dep[fa]+1;
for(ll i=0;i<G[x].size();i++){
ll y=G[x][i];
if(y==fa)continue;
dfs(y,x);r[x]+=r[y];
}
return;
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&k);
for(ll i=1;i<=m;i++){
ll x,y,w;
scanf("%lld%lld%lld",&x,&y,&w);
e[i]=(edge){x,y,w};
}
sort(e+1,e+1+m,cmp);
for(ll i=1;i<=n;i++)fa[i]=fb[i]=i;
for(ll i=0;i<k;i++){
scanf("%lld%lld",&dx[i],&dy[i]);
ll x=find(dx[i]),y=find(dy[i]);
if(x==y)continue;fa[x]=y;
}
for(ll i=1;i<=n;i++)scanf("%lld",&p[i]);
for(ll i=1;i<=m;i++){
ll x=e[i].x,y=e[i].y;
x=find(x);y=find(y);
if(x==y)continue;fa[x]=y;
fb[finb(e[i].x)]=finb(e[i].y);
}
for(ll i=1;i<=n;i++)
if(finb(i)==i)rev[i]=++cnt,fa[cnt]=cnt;
for(ll i=1;i<=n;i++)rev[i]=rev[finb(i)];
for(ll i=1;i<=n;i++)w[rev[i]]+=p[i];
memset(a,0x3f,sizeof(a));int pm=m;m=0;
for(ll i=1;i<=pm;i++){
ll x=e[i].x,y=e[i].y,w=e[i].w;
x=rev[x];y=rev[y];
if(find(x)==find(y))continue;
fa[find(x)]=find(y);
e[++m]=(edge){x,y,w};
}
sort(e+1,e+1+m,cmp);
ll MS=(1<<k);
for(ll i=0;i<k;i++)dx[i]=rev[dx[i]],dy[i]=rev[dy[i]];
for(ll s=0;s<MS;s++){
memset(mn,0x3f,sizeof(mn));
for(ll i=1;i<=cnt;i++)
fa[i]=i,G[i].clear();
bool flag=0;
for(ll i=0;i<k;i++){
if(!((s>>i)&1))continue;
ll x=find(dx[i]),y=find(dy[i]);
if(x==y){flag=1;break;}fa[x]=y;
G[dx[i]].push_back(dy[i]);
G[dy[i]].push_back(dx[i]);
}
if(flag)continue;
for(ll i=1;i<=m;i++){
ll x=find(e[i].x),y=find(e[i].y);
if(x==y)continue;fa[x]=y;
G[e[i].x].push_back(e[i].y);
G[e[i].y].push_back(e[i].x);
}
dfs(rev[1],0);
for(ll i=1;i<=m;i++){
ll x=e[i].x,y=e[i].y;
while(x!=y){
if(dep[x]<dep[y])swap(x,y);
mn[x]=min(mn[x],e[i].w);x=f[x];
}
}
ll ans=0;
for(ll i=0;i<k;i++){
if(!((s>>i)&1))continue;
ll x=dx[i],y=dy[i];
if(dep[x]<dep[y])swap(x,y);
ans+=mn[x]*r[x];
}
answer=max(answer,ans);
}
printf("%lld\n",answer);
return 0;
}