1.黑暗城堡
先求出最小生成树的每个边权，然后枚举每个点在不改变最小权值的情况下，能由多少个点转移过来，然后答案就是这些点个数的乘积
#include<bits/stdc++.h> using namespace std; const int N=1e3+10,mod=2147483647; int w[N][N],dist[N]; bool st[N]; int n,m; int prim()//先prim算法预处理处理最小生成树 { memset(dist,0x3f,sizeof dist); dist[1]=0; for(int i=0;i<n;i++) { int t=-1; for(int j=1;j<=n;j++) if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j; st[t]=true; for(int j=1;j<=n;j++) dist[j]=min(dist[j],dist[t]+w[t][j]); } int res=1; for(int i=2;i<=n;i++)//枚举每个点在不改变最小权值的情况下，能由多少个点转移过来 { int sum=0; for(int j=1;j<=n;j++) if(w[i][j]!=0x3f3f3f3f&&dist[i]==dist[j]+w[i][j]) sum++; res=(long long)res*sum%mod;//答案就是他们的乘积 } return res; } int main() { memset(w,0x3f,sizeof w); scanf("%d%d",&n,&m); int a,b,c; while(m--) { scanf("%d%d%d",&a,&b,&c); w[a][b]=w[b][a]=c; } cout<<prim()<<endl; return 0; }
2.北极通讯网络
先把小的先贪了，假如剩下连通块小于等于k个了，说明后面k个直接给他们装卫星了，不用在接无线发电机了，所以最小的d就是枚举到的w
#include<bits/stdc++.h> using namespace std; const int N=510,M=N*N; bool st[N]; int n,m,k; struct { int x,y; }q[N]; struct Edge { int a,b; double w; bool operator <(const Edge &W)const { return w<W.w; } }e[M]; int p[N]; int find(int x)//并查集 { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } double get(int i,int j)//两点间距离 { return sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y)); } int main() { int cnt=0; cin>>n>>k; for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y,p[i]=i; for(int i=0;i<n;i++) for(int j=i;j<n;j++) e[cnt++]={i,j,get(i,j)}; //Kruskal算法求最小生成树 sort(e,e+cnt);//将边从小到大排序 int ans=n; double res=0; for(int i=0;i<cnt;i++)//枚举边 { if(ans<=k) break;//假如后面可以直接装卫星了，则直接跳出 int a=e[i].a,b=e[i].b; double w=e[i].w; int pa=find(a),pb=find(b); if(pa!=pb) { ans--; p[pa]=pb; } res=w;//更新d } printf("%.2lf\n",res); return 0; }
3.新的开始
建立一个虚拟原点0，从0到i加条v的边，表示要在i这个位置修建发电站得花费v的费用，然后跑一遍最小生成树即可
#include<bits/stdc++.h> using namespace std; const int N=310; int w[N][N],dist[N]; bool st[N]; int n,m; int prim()//prim算法求最小生成树 { memset(dist,0x3f,sizeof dist); dist[0]=0; int res=0; for(int i=0;i<=n;i++) { int t=-1; for(int j=0;j<=n;j++) if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j; res+=dist[t]; st[t]=true; for(int j=0;j<=n;j++) dist[j]=min(dist[j],w[t][j]); } return res; } int main() { scanf("%d",&n); int c; for(int i=1;i<=n;i++) scanf("%d",&c),w[0][i]=c; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&c); w[i][j]=c; } printf("%d\n",prim()); return 0; }
4.构造完全图
讲解的清楚 ：传送门
分析
假设有如下图两个集合 x xx & y yy。因为要构造一个完全图，所以应该将x xx中的s [ x ] s[x]s[x]个节点与y yy中的s [ y ] s[y]s[y]个节点一一连接即连接s [ x ] ∗ s [ y ] − 1 s[x] * s[y] - 1s[x]∗s[y]−1（此处减一是为了在后面单独处理原图中的d i s [ i ] . w dis[i].wdis[i].w）个节点，为了保证此完全图的最小生成树所以要用( s [ x ] ∗ s [ y ] − 1 ) ∗ ( d i s [ i ] . w + 1 ) (s[x] * s[y] - 1) * (dis[i].w + 1)(s[x]∗s[y]−1)∗(dis[i].w+1)，最后加上原图中的d i s [ i ] . w dis[i].wdis[i].w。
解题思路：
1、用Kruskal模拟生成树
2、两个集合合成时，构建局部完全图，即假如一个集合的成员点数为n1，另一个为n2,则需要构建n1*n2条边，由贪心思想可以构建一条最小长度d，其余构建长度都为d+1，所以有sum+=d(n1*n2)-1;
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; ll res; int n; struct Edge { int a,b,w; bool operator <(const Edge&W)const { return w<W.w; } }e[N]; int p[N],s[N]; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { scanf("%d",&n); for(int i=0;i<n-1;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); e[i]={a,b,c}; } for(int i=1;i<=n;i++) p[i]=i,s[i]=1; sort(e,e+n-1); for(int i=0;i<n-1;i++) { int a=find(e[i].a),b=find(e[i].b),w=e[i].w; if(a!=b) { p[a]=b;//把集合a合并到b中 res+=(ll)(s[a]*s[b]-1)*(w+1)+w;//答案加上需要添加的边和已经有了的的边 s[b]+=s[a];//把a集合的个数+到b中 } } printf("%lld\n",res); return 0; }
5.秘密的牛奶运输
这题就是问次小生成树，我们可以先求好最小生成树，然后标记树边与非树边，在求一遍最小生成树中，两两路径的最大值，也即一个点到另一个点中的路径的最大值，然后枚举非树边，看看能不能把这条边加进来，使得树边权值变大，然后求一遍所有的生成树的最小值
这题因为不会存在环，所以可以这样做，假如有环就不行了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e2+10,M=1e4+10; int h[N],e[M],ne[M],w[M],idx; int n,m; int dist[N][N]; ll sum=0,res=1e18; struct Edge { int a,b,w; bool f; bool operator <(const Edge&W)const { return w<W.w; } }edge[M]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int p[N]; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } void kruskal() { for(int i=1;i<=n;i++) p[i]=i; for(int i=1;i<=m;i++) { int a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w; if(a!=b) { p[a]=b; sum+=w; add(a,b,w),add(b,a,w);//建立树边 edge[i].f=true; } } } void dfs(int u,int f,int maxd,int d[])//当前第u位，父节点是f，路径最大值是maxd,d是当前是距离数组 { d[u]=maxd; for(int i=h[u];~i;i=ne[i]) { int j=e[i]; if(j==f) continue; dfs(j,u,max(maxd,w[i]),d);//枚举下一个点 } } int main() { memset(h,-1,sizeof h); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&edge[i].a,&edge[i].b,&edge[i].w); sort(edge+1,edge+m+1); kruskal();//求一遍最小生成树，并建立好最小生成树 for(int i=1;i<=n;i++) dfs(i,-1,0,dist[i]);//求一下树中两两路径的最大值 for(int i=1;i<=m;i++)//枚举非树边进行替换 if(!edge[i].f) { int a=edge[i].a,b=edge[i].b,w=edge[i].w; if(dist[a][b]<w)//假如可以替换 { res=min(res,sum+w-dist[a][b]); } } printf("%lld\n",res); return 0; }
6.Tree
最小生成树无法控制白边的选取数量
于是我们就对白边增加/减少一定的值x
然后做Kruskal，记录白边的值
如果选取的数量大于need说明白边多了，则增加x（少选白边）
小于need说明白边少了，则减少x（多选白边）
如果刚好等于need，我们选择增加x
因为在能保证白边选取数量为need的时候，我们所选择的白边实际上已经固定
当x增加，白边相当于整体向后挪动，这样就可以使选择的黑边尽可能小
这样一来，我们选择的黑边是最小的，白边也是最小的，结果自然最优
ps在排序的时候边权相同时优先选择白边（和上述理解类似，请读者自行解决）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10; int n,m,k,sum; struct Edge { int a,b,w,type; bool operator <(const Edge&W)const { if(w==W.w) return type<W.type; return w<W.w; } }e[N]; int a[N],b[N],w[N],type[N]; int p[N]; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } bool judge(int x) { int cnt=0; sum=0; for(int i=0;i<=n;i++) p[i]=i; for(int i=1;i<=m;i++)//先把数全部copy过来 { e[i]={a[i],b[i],w[i],type[i]}; if(!e[i].type) e[i].w+=x;//假如是白色，则减去 } sort(e+1,e+m+1); for(int i=1;i<=m;i++) { int pa=find(e[i].a),pb=find(e[i].b); if(pa!=pb) { if(!e[i].type) cnt++;//记录白色的边有多少条 p[pa]=pb; sum+=e[i].w;//数的总权值 } } return cnt>=k; } int main() { scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) scanf("%d%d%d%d",&a[i],&b[i],&w[i],&type[i]);//先存下来数据 int l=-100,r=100,res; while(l<=r)//二分 { int mid=l+r>>1; if(judge(mid)) l=mid+1,res=sum-k*mid;//假如白色的数多了，则变大点，答案就是总得出来的树总权值减去加上的k条白色权值 else r=mid-1; } printf("%d\n",res); return 0; }
7.最小生成树计数
衍生至生成树计数，这题就问最小生成树的个数有多少个，有两种做法
借鉴于图论 —— 生成树 —— 生成树计数_Alex_McAvoy的博客-CSDN博客_生成树计数
#include<bits/stdc++.h> using namespace std; const int N=1e2+10,M=1e3+10,mod=31011; int n,m; int sum; struct Edge { int a,b,w; bool operator <(const Edge&W)const { return w<W.w; } }e[M]; struct { int l,r,cnt; }a[M];//记录不同的边在最小生成树中需要的条数 int cnta; int p[N]; int find(int x)//没有路径压缩的并查集 { if(p[x]!=x) return find(p[x]); return p[x]; } int kruskal()//求最小生成树 { int cnt=0; sort(e+1,e+1+m); for(int i=1;i<=n;i++) p[i]=i; for(int i=1;i<=m;i++) { int fa=find(e[i].a),fb=find(e[i].b),w=e[i].w; if(e[i-1].w!=w) a[cnta].r=i-1,a[++cnta].l=i;//假如不同边则加进来 if(fa!=fb) { p[fa]=fb; a[cnta].cnt++; cnt++; } } a[cnta].r=m; return cnt; } void dfs(int x,int now,int num)//处理到第x条边，现在的点是now，现在已经用了的边是num { if(now==a[x].r+1) { if(num==a[x].cnt) sum++;//假如这num条也能构成新的最小生成树，则sum++ return; } int fa=find(e[now].a),fb=find(e[now].b); if(fa!=fb)//假如不在一个集合才能选这条边 { p[fa]=fb;//把这个集合合并在一起 dfs(x,now+1,num+1);//选这条边 p[fa]=fa;//回溯，把变了的改回来 } dfs(x,now+1,num);//不选择这条边 } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w); int t=kruskal(); if(t!=n-1)//假如不能构成一棵树 { puts("0"); return 0; } int res=1; for(int i=1;i<=n;i++) p[i]=i;//初始化集合，也即并查集 for(int i=1;i<=cnta;i++)//枚举所有不同的边 { sum=0; dfs(i,a[i].l,0);//求一下这个边能有多少中方案 res=res*sum%mod;//答案就是每种边之积 for(int j=a[i].l;j<=a[i].r;j++)//把边重新加入到最小生成树中 { int fa=find(e[j].a),fb=find(e[j].b); if(fa!=fb) p[fa]=fb; } } printf("%d\n",res); return 0; }
8.次小生成树
借鉴大佬：传送门
lca倍增O(logn)求新加入非树边边的两点a,b间的最大边和最小边
理:对于一张无向图,如果存在最小生成树和次小生成树,那么对于任何一颗最小生成树都存在一颗次小生成树
使得这两棵树只有一条边不同
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+10,M=3e5+10,INF=0x3f3f3f3f; int p[N];//并查集 int h[N],e[M],ne[M],w[M],idx; int depth[N],d1[N][17],d2[N][17],f[N][17];//depth是深度，d1是某个点走2^j次方步的最大值，d2是次大值，f是某个点走2^k次方步所到达的点 int q[N]; int n,m; struct Edge { int a,b,w; bool used;//用来标记是否是树边 bool operator <(const Edge &t) const { return w<t.w; } }edge[M]; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } ll kruskal()//求最小生成树 { memset(h,-1,sizeof h);//初始化 for(int i=1;i<=n;i++) p[i]=i;//初始化 sort(edge,edge+m);//排序 ll res=0; for(int i=0;i<m;i++) { int a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w; if(a!=b)//假如不在一个集合 { p[a]=b;//合并成一个集合 res+=w;//加上这条最小生成树的边 edge[i].used=true;//标记一下是树边 add(edge[i].a,edge[i].b,w),add(edge[i].b,edge[i].a,w);//建树图 } } return res;//返回最小生成树的权值和 } void bfs()//求 深度 最大值 次大值 每个点走几步由那个点更新过来 { memset(depth,0x3f,sizeof depth); depth[0]=0,depth[1]=1;//0号点是避免跳出去，1号点初始化深度为1 int hh=0,tt=0; q[0]=1;//1号点入队 while(hh<=tt) { int t=q[hh++]; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(depth[j]>depth[t]+1)//假如没有更新过 { depth[j]=depth[t]+1;//则更新深度 q[++tt]=j;//把这个点入队 f[j][0]=t;//j这个点走2^0=1步是t d1[j][0]=w[i],d2[j][0]=-INF;//j这个点向上走2^0=1步的最大值是w[i],次大没有标记为负无穷 for(int k=1;k<=16;k++)//更新跳到的点 { int anc=f[j][k-1];//表示由那个点跳过来的 int d[4]={d1[anc][k-1],d2[anc][k-1],d1[j][k-1],d2[j][k-1]};//把j~anc~k的最大次大加到d中 f[j][k]=f[anc][k-1];//更新跳的点 d1[j][k]=d2[j][k]=-INF;//先初始化为负无穷 for(int u=0;u<4;u++)//求一遍最大和次大 { int dist=d[u]; if(dist>d1[j][k]) d2[j][k]=d1[j][k],d1[j][k]=dist; else if(dist!=d1[j][k]&&dist>d2[j][k]) d2[j][k]=dist; } } } } } } int lca(int a,int b,int w)//用来求最大值与次大值能否更新 { static int d[2*N]; int cnt=0; if(depth[a]<depth[b]) swap(a,b);//假如a深度低，则交换 for(int k=16;k>=0;k--)//让a与b同个深度 if(depth[f[a][k]]>=depth[b])//假如还是大，则继续跳 { //把他们跳过的位置的最大值与次大值都记录下来 d[cnt++]=d1[a][k]; d[cnt++]=d2[a][k]; a=f[a][k];//更新跳的点 } if(a!=b)//假如还没跳到一起，也就是没找到最近公共祖宗 { for(int k=16;k>=0;k--)//让a和b一起跳 if(f[a][k]!=f[b][k]) { //把他们跳过的位置的最大值与次大值都记录下来 d[cnt++]=d1[a][k]; d[cnt++]=d2[a][k]; d[cnt++]=d1[b][k]; d[cnt++]=d2[b][k]; a=f[a][k],b=f[b][k];//更新跳过的位置 } //最后也要把跳到最近公共祖先的位置也记录下来 d[cnt++]=d1[a][0]; d[cnt++]=d2[a][0]; d[cnt++]=d1[b][0]; d[cnt++]=d2[b][0]; } int dist1=-INF,dist2=-INF; for(int i=0;i<cnt;i++)//求一遍最大值和次大值 { int dist=d[i]; if(dist>dist1) dist2=dist1,dist1=dist; else if(dist!=dist1&&dist>dist2) dist2=dist; } if(w>dist1) return w-dist1;//假如最大值可以用来更新 if(w>dist2) return w-dist2;//反之次大值可以用来更新 return INF;//反之为正无穷 } int main() { scanf("%d%d",&n,&m); for(int i=0;i<m;i++) { int a,b,w; scanf("%d%d%d",&a,&b,&w); edge[i]={a,b,w}; } ll sum=kruskal();//求一下最小生成树的权值和 bfs();//求深度 最大值 次大值 更新的点 ll res=1e18; for(int i=0;i<m;i++) if(!edge[i].used)//假如是非树边 { int a=edge[i].a,b=edge[i].b,w=edge[i].w; res=min(res,sum+lca(a,b,w));//求一遍最大值与次大值能否用来更新 } printf("%lld\n",res); return 0; }
