The Unique MST

题解：次小生成树

C++版本一

Prim算法

/*
*@Author:   STZG
*@Language: C++
*/
//#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int mapp[N][N];
bool vis[N],connect[N][N];
int dis[N],maxd[N][N],per[N];
void Init()
{
    memset(mapp,INF,sizeof(mapp));
    memset(connect,false,sizeof(connect));
}
int prim()
{
    memset(maxd,0,sizeof(maxd));
    memset(vis,false,sizeof(vis));
    for(int i = 1;i <= n;i ++)
    {
        dis[i] = mapp[1][i];per[i] = 1;//首先父亲节点都是根节点
    }
    vis[1] = 1;
    dis[1] = 0;
    int res = 0;
    for(int i = 1;i < n;i ++){
        int index = -1,temp  = INF;
        for(int j = 1;j <= n;j ++){
            if(!vis[j] && dis[j] < temp){
                index = j;temp = dis[j];
            }
        }
        if(index == -1) return res;
        vis[index] = 1;
        connect[index][per[index]] = false;connect[per[index]][index] = false;//这条边已经在最小生成树中，后面我们就不能添加这条边了
        res += temp;
        maxd[per[index]][index]=maxd[index][per[index]]=temp;//更新点之间的最大值
        for(int j=1;j<=n;j++){
            if(j != index && vis[j]){//只是更新我们已经遍历过来的节点
            maxd[index][j]=maxd[j][index]=max(maxd[j][per[index]],dis[index]);
            }
                if(!vis[j] && mapp[index][j] < dis[j]){
                dis[j] = mapp[index][j];
                per[j] = index;
            }
        }
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    int T;
    scanf("%d\n",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        Init();
        int u,v,w;
        for(int i = 0;i < m;i ++){
            scanf("%d%d%d",&u,&v,&w);
            mapp[u][v] = w;mapp[v][u]  = w;
            connect[u][v] = true;connect[v][u] = true;
        }
        int ans = prim();
        bool over = false;
        //如果有某条边没有被最小生成树使用，并且i~j的最大值大于图中得到最大值，那么就表示次小生成树存在
        //相反就不会存在
        for(int i = 1;!over && i <= n;i ++)
        for(int j = 1;j <= n;j ++){
            if(connect[i][j] == false || mapp[i][j] == INF)
                continue;
            if(mapp[i][j] == maxd[i][j])//当边长度相同是就是表示最小生成树相同
            {
                over = 1;
                break;
            }
        }
        if(over)
            printf("Not Unique!\n");
        else
            printf("%d\n",ans);
    }//如果我们需要求解次小生成树的权值时，我们就要把在最小生成树中没有用过的边，加上然后减去对应环中最大的路径
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f
#define FI first
#define SE second
#define MP make_pair
#define PI pair<int,int>
#define lson l,m,rt<<1,ls,rs
#define rson m+1,r,rt<<1|1,ls,rs
#define test printf("here!!!\n")
using namespace std;
const int mx=100+10;
int n,m;
int dis[mx];
int vis[mx];
int mp[mx][mx];
int sum;
int maxd[mx][mx];
int pre[mx];
int connect[mx][mx];
void prim()
{
    sum=0;
    memset(maxd,0,sizeof(maxd));
    memset(connect,0,sizeof(connect));
    for (int i=1;i<=n;++i)
    {
        dis[i]=mp[1][i];
        pre[i]=1;
        vis[i]=0;
    }
    dis[1]=0;
    vis[1]=1;
    int now=1;
    for (int i=1;i<n;++i)
    {
        int minn=INF;
        for (int j=1;j<=n;++j)
        {
            if (!vis[j]&&minn>dis[j])
            {
                minn=dis[j];
                now=j;
            }
        }
        sum+=dis[now];
        vis[now]=1;
        connect[now][pre[now]]=connect[pre[now]][now]=1;
        for (int j=1;j<=n;++j)
        {
            if (vis[j])
            {
                maxd[j][now]=maxd[now][j]=max(maxd[j][pre[now]],dis[now]);
            }
            else if (dis[j]>mp[now][j])
            {
                dis[j]=mp[now][j];
                pre[j]=now;
            }
        }
    }
}
int sprim()
{
    int ans=INF;
    for (int i=1;i<=n;++i)
    {
        for (int j=i+1;j<=n;++j)
        {
            if (!connect[i][j]&&mp[i][j]!=INF)
            {
                ans=min(ans,sum+mp[i][j]-maxd[i][j]);
            }
        }
    }
    return ans;
}
int main()
{
    int x,y,w,t;
    scanf("%d",&t);
    while (t--)
    {
        memset(mp,INF,sizeof(mp));
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;++i)
        {
            scanf("%d%d%d",&x,&y,&w);
            mp[x][y]=w;
            mp[y][x]=w;
        }
        prim();
        int res=sprim();
        if (sum==res) printf("Not Unique!\n");
        else printf("%d\n",sum);
    }
}

C++版本三

Kruskal算法

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define pb push_back
#define INF 0x3f3f3f3f
#define FI first
#define SE second
#define MP make_pair
#define PI pair<int,int>
#define lson l,m,rt<<1,ls,rs
#define rson m+1,r,rt<<1|1,ls,rs
#define test printf("here!!!\n")
using namespace std;
const int mx=1e4+10;
const int MX=5e3+10;
int n,m;
struct Node
{
    int st;
    int to;
    ll w;
    friend bool operator <(const Node &a,const Node &b)
    {
        return a.w<b.w;
    }
}vec[MX];
int use[MX];
int pre[mx],sz[mx];
int fa[mx][20];
int ma[mx][20];
int lg[mx];
int dis[mx];
int vis[mx];
struct Eg
{
    int to;
    ll w;
    int nxt;
}edge[MX*2];
int head[mx];
int cnt=0;
ll sum=0;
void add(int u,int v,ll w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt;
}
void init()
{
    cnt=0;
    sum=0;
    lg[0]=-1;
    for (int i=1;i<=n;++i) lg[i]=lg[i>>1]+1;
    for (int i=1;i<=n;++i)
    {
        head[i]=0,dis[i]=0,vis[i]=0,pre[i]=i,sz[i]=1;
    }
    memset(ma,0,sizeof(ma));
    memset(fa,0,sizeof(fa));
    memset(use,0,sizeof(use));
    dis[0]=-1;
}
int unfd(int x)
{
    int r=x;
    while (r!=pre[r]) r=pre[r];
    int t;
    while (x!=pre[x])
    {
        t=pre[x];
        pre[x]=r;
        x=t;
    }
    return r;
}
int unjoin(int x,int y)
{
    int fx=unfd(x),fy=unfd(y);
    if (fx!=fy)
    {
        if (sz[fx]<sz[fy])
        {
            pre[fx]=fy;
            sz[fy]+=sz[fx];
        }
        else
        {
            pre[fy]=fx;
            sz[fx]+=sz[fy];
        }
        return 1;
    }
    return 0;
}
void kruskal()
{
    int tot=n-1;
    for (int i=1;i<=m;++i)
    {
        if (unjoin(vec[i].st,vec[i].to))
        {
            --tot;
            sum+=vec[i].w;
            use[i]=1;
            add(vec[i].st,vec[i].to,vec[i].w);
            add(vec[i].to,vec[i].st,vec[i].w);
        }
        if (!tot) break;
    }
}
void dfs(int st,int fath)
{
    vis[st]=1;
    dis[st]=dis[fath]+1;
    fa[st][0]=fath;
    for (int i=1;(1<<i)<=dis[st];++i)
    {
        fa[st][i]=fa[fa[st][i-1]][i-1];
        ma[st][i]=max(ma[st][i-1],ma[fa[st][i-1]][i-1]);
    }
    for (int i=head[st];i;i=edge[i].nxt)
    {
        if (!vis[edge[i].to])
        {
            ma[edge[i].to][0]=edge[i].w;
            dfs(edge[i].to,st);
        }
    }
}
int LCA(int u,int v)
{
    int maxn=0;
    if (dis[u]<dis[v]) swap(u,v);
    while (dis[u]>dis[v])
    {
        int loog=lg[dis[u]-dis[v]];
        maxn=max(ma[u][loog],maxn);
        u=fa[u][loog];
    }
    if (u==v) return maxn;
    for (int i=lg[dis[u]];i>=0;--i)
    {
        if (fa[u][i]!=fa[v][i])
        {
            maxn=max(max(ma[u][i],ma[v][i]),maxn);
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return max(max(ma[u][0],ma[v][0]),maxn);
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        scanf("%d%d",&n,&m);
        int x,y;
        ll z;
        init();
        for (int i=1;i<=m;++i)
        {
            scanf("%d%d%lld",&vec[i].st,&vec[i].to,&vec[i].w);
        }
        sort(vec+1,vec+m+1);
        kruskal();
        dfs(1,0);
        ll ans=0x3f3f3f3f3f3f3f3f;
        for (int i=1;i<=m;++i)
        {
            if (!use[i])
            {
                ans=min(ans,sum-LCA(vec[i].st,vec[i].to)+vec[i].w);
            }
        }
        if (ans==sum) printf("Not Unique!\n");
        else printf("%lld\n",sum);
    }
}

C++版本四

#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
 
using namespace std;
int n,m;
struct data
{
    int u,v,w;
    bool vis;
} p[20010];
vector<int>G[110];
int per[110],maxd[110][110];
bool cmp(data a,data b)
{
    return a.w < b.w;
}
int Union_Find(int x)
{
    return x == per[x] ? x: per[x] = Union_Find(per[x]);
}
void kruskal()
{
    sort(p,p+m,cmp);
    for(int i=0; i<=n; i++)//初始化
    {
        G[i].clear();
        G[i].push_back(i);
        per[i]=i;
    }
    int sum=0,k=0;//sum是最小生成树的值
    for(int i=0; i<m; i++)
    {
        if(k==n-1)  break;
        int x1=Union_Find(p[i].u),x2=Union_Find(p[i].v);
        if(x1!=x2)
        {
            k++;
            p[i].vis=1;//这条边已经用过了
            sum+=p[i].w;
            int len_x1=G[x1].size();
            int len_x2=G[x2].size();
            for(int j=0; j<len_x1; j++)//更新两点之间距离的最大值
                for(int k=0; k<len_x2; k++)
                    maxd[G[x1][j]][G[x2][k]]=maxd[G[x2][k]][G[x1][j]]=p[i].w;//因为后面的边会越来越大，所以这里可以直接等于当前边的长度
            per[x1]=x2;
            //因为per[x1] = x2,在Union_Find函数中要寻找和x1相关联节点的跟节点的时候，都会找到x2，所以这里不用再去更新和x1节点相连的节点
            //十分感谢Self-Discipline博主，提出此问题
//            int tem[110];
//            for(int j=0; j<len_x2; j++)//现在已经属于一棵树了，那么我们就将点添加到相应的集合中
//                tem[j]=G[x2][j];
            for(int j=0; j<len_x1; j++)
                G[x2].push_back(G[x1][j]);
//            for(int j=0; j<len_x2; j++)
//                G[x1].push_back(tem[j]);
        }
    }
    int cisum=INF;//次小生成树的权值
    for(int i=0; i<m; i++)
        if(!p[i].vis)
            cisum=min(cisum,sum+p[i].w-maxd[p[i].u][p[i].v]);
    if(cisum>sum)
        printf("%d\n",sum);
    else
        printf("Not Unique!\n");
}
int main()
{
    int T;
    scanf("%d\n",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0; i<m; i++)
        {
            scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].w);
            p[i].vis = false;
        }
        kruskal();
    }
    return 0;
}

全部评论

推荐最新楼层

12-03 16:53

中国科学技术大学 Java

关于暑期实习时间的问题

想问问各位佬，暑期实习可以5月前入职然后持续7个月以上吗？因为学校实习论文要求7个月的连续实习作为论文，自己日常实习大概本月才能入职，如果将这段日常作为论文，那必须连续实习七个月，明年的暑期实习就没时间了但是暑期实习对秋招还是很重要，所以想着到时候假如能找到暑期，直接把日常辞了，用暑期当论文，不知道时间上是否可行

点赞评论收藏

12-03 18:43

已编辑

华南理工大学数据分析师

终于等到你，还好我没放弃！

上周在床上刷手机，突然收到广发卡面试通知，属实是垂死病中惊坐起，没想到校招快结束了竟然又收到面试邀请了，果然金融大厂诚不欺我啊，并且还能选线上or线下，感觉在银行招聘里属于比较人性化了。说实在的，很多uu们估计也跟我一样，从7月起兵到现在，结果是一个像样的offer都没有。本来10月的时候还觉得有希望，偶尔还能有一两个面试，但是到11月已经没有什么新的岗位了，能做的只有等，已经一度想要备战明年春招了。所以收到面试邀请的那一刻，瞬间又开启战斗模式！今天视频面试，早早测好了网络环境，提前30min签到，面前抓了抓头发，一气呵成~总共5个面试官，都挺有礼貌，不会很高冷，全程开着摄像头，视频...

查看5道真题和解析

点赞评论收藏

11-07 12:09

门头沟学院大数据开发工程师

终于拿到了校招offer 太牛了数开

投票

终于拿到了校招offer 太牛了  数开

收到想要的offer：接offer

点赞评论收藏

10-16 12:29

携程_移动安全研发

转正了呀

Yushuu：你的确很厉害，但是有一个小问题：谁问你了？我的意思是，谁在意？我告诉你，根本没人问你，在我们之中0人问了你，我把所有问你的人都请来 party 了，到场人数是0个人，誰问你了？WHO ASKED？谁问汝矣？誰があなたに聞きましたか？누가 물어봤어？我爬上了珠穆朗玛峰也没找到谁问你了，我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒，在找到谁问你之前我连癌症的解药都发明了出来，我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了😆

点赞评论收藏