题目描述
翻译一下题意:给定一张N个点M条边的无向图 ,求一个无向图的最小生成树,并且满足一号节点的度不超过给定的S.
算法思路:
- process1:去除一号节点,无向图将会划分为多个连通块(T个)。
- process2:求每个连通块内部的最小生成树。
- process3:从每个连通块中选出一个节点p与1号节点相连,其中无向图边(1,p)的权值最小。此时得到了一个非最优的生成树(1的度为T)
- process4:进行S-T次替换,让生成树更优:在生成树中求每个点到1节点的路径中边权最大的值w。扫描1节点非生成树中的边(1,x,z),找到w-z 最大点x,用(1,x,z)替换路径中最大边权的边。或w-z<=0停止。
*
C++ 代码实现:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5,inf=1<<29;
typedef long long ll;
#define max(a,b) (a>=b?a:b)
#define min(a,b) (a>=b?b:a)
struct node{
int u,v,w;
friend bool operator < (node a,node b){
if(a.w>=b.w) return 0;
return 1;
}
}edge[maxn];
map<string,int> mp;
int n,tot,s,pre[maxn],ans,block[maxn],pos[maxn],vis[maxn],g[100][100],link1[100];
vector<pair<int,int> > ar;
int get(int x){
if(x==pre[x]) return x;
return pre[x]=get(pre[x]);
}
void dfs(int now){ //每个节点到1节点路径中的最大边权
for(int i=2;i<=tot;i++){ //复杂度:O(N)级别
if(g[now][i]>inf) continue;
if(edge[i].w==-1){ //访问标记
if(edge[now].w>g[now][i])
edge[i]=edge[now];
else {
edge[i].u=now;
edge[i].v=i;
edge[i].w=g[now][i];
}
dfs(i);
}
}
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
cin>>n;
memset(g,0x3f,sizeof(g)) ;
mp["Park"]=++tot;
for(int i=1;i<=n;i++){
string s1,s2;
int w;
cin>>s1>>s2>>w;
if(!mp.count(s1)) mp[s1]=++tot; //点数
if(!mp.count(s2)) mp[s2]=++tot;
edge[i].u=mp[s1],edge[i].v=mp[s2]; //离散化
edge[i].w=w;
}
//for(int i=1;i<=tot;i++) g[i][i]=0;
cin>>s;
sort(edge+1,edge+1+n); //边数目
for(int i=1;i<=tot;i++) pre[i]=i; //point
memset(link1,0x3f,sizeof(link1));
for(int i=1;i<=n;i++){ //运行Kruskal算法
int x=get(edge[i].u);
int y=get(edge[i].v);
if(x==y) continue;
if(edge[i].u==1||edge[i].v==1 ) {
ar.push_back(make_pair(max(edge[i].u,edge[i].v),edge[i].w ) );
link1[max(edge[i].u,edge[i].v)]=edge[i].w;//与1相邻的边
continue ;
}
g[edge[i].u][edge[i].v]=g[edge[i].v][edge[i].u]=edge[i].w;//生成树中的边
pre[y]=x;
ans+=edge[i].w;
}
//divede linked block
for(auto it:ar){
int v=it.first,x=get(v) ;
if(block[x]>it.second||pos[x]==0){
pos[x]=v;
block[x]=it.second;
}
}
int num=0; //连通块数目
for(int i=2;i<=tot;i++){
int x=get(i);
if(vis[x]==0){
ans+=block[x];
g[1][pos[x]]=g[pos[x]][1]=block[x]; //添加边
num++;
vis[x] = 1 ; //与1相连的在连通块中
}
}
while(s>num){ //进行生成树中边替换
s--;
int now=0,id=0;
memset(edge,-1,sizeof(edge));//表示v这个点
dfs(1);
for(auto it:ar){
int j=it.first; //j不在生成树中
if(now<edge[j].w-link1[j]&&g[1][j]>inf){
now=edge[j].w-link1[j];
id=j;
}
}
if(now<=0) break; //结束
ans-=now; //优化
g[1][id]=g[id][1]=link1[id] ; //add edge
g[edge[id].u][edge[id].v]=g[edge[id].v][edge[id].u]=inf+1;//delete edge
}
cout<<"Total miles driven: "<<ans<<endl;
return 0;
}