考察:最(次)小生成树
思路:
很明显是求解严格次小生成树.
在当前图所有能构造树的方法中,边权和是第二大的生成树.
求次小生成树的两种方法:
1.先求最小生成树,枚举删取最小生成树的一条边,然后再做最小生成树 时间复杂度O(mlog2 m+nm)
但只能求非严格次小生成树
2.先求最小生成树,然后依次枚举非树边,然后将该边加入树中,同时去掉树中一条边,使图还是一棵生成树.
答案为 最小生成树的权值和-去掉的边+新加入的边.
时间复杂度O(n2+mlog2 m+m)
n2
严格次小生成树和非严格都可以求
因为本题是求严格次小生成树,所以只能用方法二.方法二总体步骤为:
1.求最小生成树,标记哪些边是非树边,哪些是树边.
2.预处理最小生成树上两点之间的最大边
3.枚举每一条非树边.
但是第二步不能仅仅求最大边,因为存在最大边和枚举的非树边长度相等的情况,如果只有一条非树边就求不出次小生成树,此时我们要用次大边.
1 #include <iostream> 2 #include <cstring> 3 #include <vector> 4 #include <algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int N = 510,M = 10010; 8 struct Road{ 9 int u,v,w; 10 bool vis; 11 bool operator<(const Road r)const{ 12 return this->w<r.w; 13 } 14 }road[M]; 15 struct Paht{ 16 int to,ne,w; 17 }path[M<<1]; 18 int n,m,p[N],h[N],idx,d1[N][N],d2[N][N]; 19 LL sum; 20 int findf(int x) 21 { 22 if(x!=p[x]) p[x] = findf(p[x]); 23 return p[x]; 24 } 25 void add(int a,int b,int w) 26 { 27 path[idx].to =b ,path[idx].w = w,path[idx].ne = h[a],h[a] = idx++; 28 } 29 void init() 30 { 31 for(int i=1;i<=m;i++) 32 { 33 int pa = findf(road[i].u),pb = findf(road[i].v); 34 if(pa==pb) continue; 35 p[pa] = pb; 36 sum+=(LL)road[i].w; 37 add(road[i].u,road[i].v,road[i].w); add(road[i].v,road[i].u,road[i].w); 38 road[i].vis = 1;//树边 39 } 40 } 41 void dfs(int u,int fa,int m1,int m2,int gr) 42 { 43 d1[gr][u] = m1,d2[gr][u] = m2; 44 for(int i=h[u];~i;i=path[i].ne) 45 { 46 int v = path[i].to,w = path[i].w; 47 if(v==fa) continue; 48 int maxn1 = m1,maxn2 = m2; 49 if(w>maxn1) maxn2 = maxn1,maxn1 = w; 50 else if(w<maxn1&&w>maxn2) maxn2 = w; 51 dfs(v,u,maxn1,maxn2,gr); 52 } 53 } 54 int main() 55 { 56 scanf("%d%d",&n,&m); 57 for(int i=1;i<=n;i++) p[i] = i,h[i] = -1; 58 for(int i=1;i<=m;i++) 59 { 60 int u,v,w; scanf("%d%d%d",&u,&v,&w); 61 road[i] = {u,v,w,0}; 62 } 63 sort(road+1,road+m+1); 64 init(); 65 for(int i=1;i<=n;i++) 66 dfs(i,-1,0,0,i); 67 LL res = 1e14; 68 for(int i=1;i<=m;i++) 69 if(!road[i].vis) 70 { 71 int u = road[i].u,v = road[i].v; 72 if(road[i].w>d1[u][v]) res = min(sum+road[i].w-d1[u][v],res); 73 else res = min(sum+road[i].w-d2[u][v],res); 74 } 75 printf("%lld\n",res); 76 return 0; 77 }