图论板子次小生成树-白红宇

图论板子次小生成树

阅读量：4493 次

发布时间：2019-06-08

本文共 2670 字，大约阅读时间需要 8 分钟。

由最小生成树T进行一次可行交换得到的新的生成树的集合称为T的邻集 N(T)

(即最小生成树的某两节点间有重边可替换或原图中存在其它边可重新连接这些节点)

找到可替换边中权值最小的那条替换即可

实现：存最小生成树上每两点间最大距离，

遍历每条不在最小生成树上的边，更新以这条边替换该边两端节点间的最大距离后的最小值

在kruskal算法基础上实现

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;const int INF=0x3f3f3f3f;typedef pair
              
                pr;typedef long long ll;#define fi first#define se second#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))#define N 10000+5struct node{ int u, v, w; bool vis;}e[4*N];bool cmp(node a, node b){ if(a.w==b.w && a.u==b.u) return a.v

g[1005];int fin(int x){ int r=x; while(r!=p[r]) r=p[r]; int i=x, t; while(p[i]!=r) { t=p[i]; p[i]=r; i=t; } return r;}void kruskal(){ sort(e, e+m, cmp); int i, j, l; for(i=0; i<=n; i++) p[i]=i, g[i].clear(), g[i].push_back(i); int k=0, sum=0, maxn[105][105]; for(i=0; i

>t; while(t--) { cin>>n>>m; for(i=0; i

>e[i].u>>e[i].v>>e[i].w, e[i].vis=false; kruskal(); }}

#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<cstring>#include<cmath>#include<queue>#include<set>#include<string>using namespace std;const int INF=0x3f3f3f3f;typedef pair<int, int> pr;typedef long long ll;#define fi first#define se second#define me(x) memset(x, -1, sizeof(x))#define mem(x) memset(x, 0, sizeof(x))#define N 10000+5struct node{ int u, v, w; bool vis;}e[4*N];

bool cmp(node a, node b){ if(a.w==b.w && a.u==b.u) return a.v<b.v; if(a.w==b.w) return a.u<b.u; return a.w<b.w;}int n, m;int p[N];vector<int> g[1005];

int fin(int x){ int r=x; while(r!=p[r]) r=p[r]; int i=x, t; while(p[i]!=r) { t=p[i]; p[i]=r; i=t; } return r;}void kruskal(){ sort(e, e+m, cmp); int i, j, l; for(i=0; i<=n; i++) p[i]=i, g[i].clear(), g[i].push_back(i); int k=0, sum=0, maxn[105][105];

for(i=0; i<m; i++) { if(k==n-1) break; int x=fin(e[i].u), y=fin(e[i].v); if(x!=y) {

k++; p[y]=x; e[i].vis=true; sum+=e[i].w; int lenx=g[x].size(), leny=g[y].size(); for(j=0; j<lenx; j++) for(l=0; l<leny; l++) maxn[g[x][j]][g[y][l]]=maxn[g[y][l]][g[x][j]]=e[i].w; //更新两点间最大值(kruskal保证边权递增 int tmp[1005]; for(j=0; j<lenx; j++) tmp[j]=g[x][j]; for(l=0; l<leny; l++) g[x].push_back(g[y][l]);//加点 for(j=0; j<lenx; j++) g[y].push_back(tmp[j]);//加点 } } int sum1=INF; for(i=0; i<m; i++) if(!e[i].vis) sum1=min(sum1, sum+e[i].w-maxn[e[i].u][e[i].v]); //更新替换后的最小值 //cout<<sum<<endl<<sum1<<endl; if(sum<sum1) cout<<sum<<endl; else cout<<"Not Unique!"<<endl;}

int main(){ int i, j, k, t; cin>>t; while(t--) { cin>>n>>m; for(i=0; i<m; i++) cin>>e[i].u>>e[i].v>>e[i].w, e[i].vis=false; kruskal(); }}

转载于:https://www.cnblogs.com/op-z/p/11281912.html

你可能感兴趣的文章