【AtCoder Regular Contest 078 F】Mole and Abandoned Mine | Mrsrz's blog

随机化。

题目大意：

给定一个 $n$ 个点 $m$ 条边的无向连通图，每条边有边权。

现在要割掉一些边，使得 $1$ 到 $n$ 只有一条不经过重复点的路径。

问割掉的最小权值是多少。

题解：

最后剩下的图一定是原图的一棵生成树上加一些边。

我们如果已经知道生成树的样子，则剩下的边能不能连也可以确定。

由于 $n$ 和 $m$ 较小，时限也比较宽松，所以我们可以多次对边进行 random_shuffle，然后找到一棵生成树，然后求此时的最优解。一直随机直到时间用完为止。

Code：

#include<iostream>
#include<random>
#include<ctime>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=500;
mt19937 mt(time(0));
struct edge{
    int u,v,w;
}e[N];
int n,m,ans=0x3fffffff,fa[16],nww,sum,rt[16];
bool con[N];
vector<int>G[16];
inline int find(int x){while(x!=fa[x])x=fa[x]=fa[fa[x]];return x;}
void dfs(int now,int pre=0){
    for(int to:G[now])if(to!=pre)fa[to]=now,dfs(to,now);
}
void dfs2(int now){
    for(int to:G[now])if(!rt[to])rt[to]=rt[now],dfs2(to);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        sum+=w;
        e[i]=(edge){u,v,w};
    }
    while(1.*clock()/CLOCKS_PER_SEC<3.9){
        shuffle(e+1,e+m+1,mt);
        memset(con,0,sizeof con);
        for(int i=1;i<=n;++i)fa[i]=i,G[i].clear(),rt[i]=0;
        nww=sum;
        for(int i=1;i<=m;++i){
            int x=find(e[i].u),y=find(e[i].v);
            if(x!=y)nww-=e[i].w,con[i]=1,fa[y]=x,
            G[e[i].u].push_back(e[i].v),G[e[i].v].push_back(e[i].u);
        }
        fa[1]=0,dfs(1);
        for(int i=n;i;i=fa[i])rt[i]=i;
        for(int i=n;i;i=fa[i])dfs2(i);
        for(int i=1;i<=m;++i)if(!con[i]&&rt[e[i].u]==rt[e[i].v])nww-=e[i].w;
        if(nww<ans)ans=nww;
    }
    cout<<ans<<'\n';
    return 0;
}