两种方法
1.Kruskal算法（解决疏松图）
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define maxm 500000
int father[maxm],n,m,cnt,ans;
struct edge
{
int x,y,z;
bool operator < (const edge &s) const
{
return z<s.z;
}
}a[maxm];
int getfather(int x)
{
if(father[x]==x)
return x;
father[x]=getfather(father[x]);
return father[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
}
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)
{
int fx,fy;
fx=getfather(a[i].x);
fy=getfather(a[i].y);
if(fx==fy) continue;
father[fx]=fy;
cnt++;
ans+=a[i].z;
}
if(cnt!=n-1)
puts("orz
");
else printf("%d
",ans);
return 0;
}
2.Prim算法（解决稠密图）复杂度O((n+m)logm)
类似dijkstra
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int maxm=1e6+7;
int pre[maxm],last[200007],other[maxm],len[maxm];
int dis[200007];
bool vis[200007];
int n,m,l,cnt;
priority_queue<pair<int,int > >q;
ll ans;
void add(int x,int y,int z)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
len[l]=z;
}
void prim()
{
memset(dis,63,sizeof(dis));
dis[1]=0;
q.push(make_pair(0,1));
while(q.size()&&cnt<n)
{
int d=q.top().first,u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=1;
cnt++;
ans+=-d;
for(int p=last[u];p;p=pre[p])
{
int v=other[p];
if(dis[v]>len[p])
{
dis[v]=len[p];
q.push(make_pair(-dis[v],v));
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
prim();
printf("%lld
",ans);
return 0;
}
例题
1.黑暗城堡
做法：跑一遍dijkstra，算出d[i]，prim算法中判断相等，在利用乘法原理即可
2.北极通讯网络
做法:直接Kruskal,当边数连到n-k时就直接输出即可
3.新的开始
做法:建立一个0节点，把建立电站的费用当做0和当前节点建了一条边，剩下的就是模板了
4.构造完全图
做法：类似prim的思想，cnt[i]表示i所在的连通块的点数，最小生成树的树边把树隔成两部分，连边数为cnt[i] * cnt[j]-1(-1因为最小生成树的数边不算)，边长应为树边权值+1，然后i，j并查集即可
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int maxm=1e5+7;
int n;
struct node
{
int x,y;
int l;
bool operator < (const node &s ) const
{
return l<s.l;
}
}a[maxm];
ll ans;
int cnt[maxm],f[maxm];
int find(int x){
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].l);
ans+=a[i].l;
}
for(int i=1;i<=n;i++)
f[i]=i,cnt[i]=1;//类似prim算法中的集合概念
sort(a+1,a+n);
for(int i=1;i<=n-1;i++)//从小往大枚举，保证最小生成树唯一
{
int fx=find(f[a[i].x]);
int fy=find(f[a[i].y]);
if(fx!=fy)
{
f[fx]=fy;
ans+=(ll)(cnt[fx]*cnt[fy]-1)*(ll)(a[i].l+1);
cnt[fy]+=cnt[fx];
}
}
printf("%lld
",ans);
return 0;
}
5.秘密的牛奶运输
做法：严格次小生成树。先进行最小生成树，把加进来的边打标记，建边，把lca的基本量求出来，另加上最大边权和次大边权，(maxx[i][j])表示从i点往上跳(2^{j})期间经过边的最大值,(mini[i][j])表示从i点往上跳(2^{j})期间经过边的严格次大值。
for(int j=1;j<=19;j++)
{
for(int i=1;i<=n;i++)
{
jump[i][j]=jump[jump[i][j-1]][j-1];
maxx[i][j]=max(maxx[i][j-1],maxx[jump[i][j-1]][j-1]);
if(maxx[i][j-1]==maxx[jump[i][j-1]][j-1])
mini[i][j]=max(mini[i][j-1],mini[jump[i][j-1]][j-1]);
else if(maxx[i][j-1]<maxx[jump[i][j-1]][j-1])
mini[i][j]=max(maxx[i][j-1],mini[jump[i][j-1]][j-1]);
else
mini[i][j]=max(mini[i][j-1],maxx[jump[i][j-1]][j-1]);
}
}
求完之后，枚举未加进来的边，将两端点向LCA进行倍增搜索，搜出最大边权，如果一样，找出次大边权（保证严格次小），进行替换即可
int qmax(int x,int y,int z)
{
int ans=-1;
for(int j=0;j<=19;j++)
{
if((dep[x]-dep[y])&(1<<j))
{
if(maxx[x][j]!=z)
ans=max(maxx[x][j],ans);
else ans=max(mini[x][j],ans);
x=jump[x][j];
}
}
return ans;
}
for(int i=1;i<=m;i++)
{
if(!vis[i])
{
int x=a[i].x;
int y=a[i].y;
int d=a[i].l;
int xy=lca(x,y);
int l1=qmax(x,xy,d);
int l2=qmax(y,xy,d);
ans=min(ans,cnt-max(l1,l2)+d);
}
}
6.Tree
做法:玄学做法，二分+最小生成树。给白边加上一个偏移量k,k∈([-100,100])。二分k，给白边加上K,进行Krusal。如果白边超过cnt，说明如果再缩小k,选边将更多，所以要扩大k。反之亦然。
bool check(int mid)
{
tot=0;
for(int i=0;i<=n-1;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
if(!a[i].color)
a[i].l+=mid;
}
sort(a+1,a+m+1);
int num=0;
for(int i=1;i<=m;i++)
{
int fx=find(a[i].x);
int fy=find(a[i].y);
if(fx!=fy)
{
f[fx]=fy;
tot+=a[i].l;
num+=a[i].color^1;
}
}
for(int i=1;i<=m;i++)
{
if(!a[i].color)
a[i].l-=mid;
}
if(num<cnt) return 0;
else return 1;
}
int l=-100,r=100;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
l=mid+1;
ans=tot-cnt*mid;
}
else r=mid-1;
}
7.最小生成树计数
做法：应用最小生成树的两条性质：
1.不同的最小生成树中,每种权值的边出现的个数是确定的
2.不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的
此时需要记录所有的边权种类，最小生成树需要的种类边权个数，暴力二进制枚举选还是不选即可。注意：此题并查集不能用路径压缩，因为要快速判断连通块。
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int maxm=2007;
const ll mo=31011;
struct node
{
int x,y;
int l;
bool operator < (const node &s) const
{
return l<s.l;
}
}a[maxm];
int n,m;
int f[maxm];
ll ans=1,res;
struct lt
{
int l,r,cnt;
}b[maxm];
int find(int x)//为了能够快速分开连通块，并查集中不能使用路径压缩
{
return f[x]==x ? x : find(f[x]);
}
void dfs(int x,int l,int sum)
{
if(l>b[x].r){
if(sum==b[x].cnt)
res++;
return;
}
int fx=find(a[l].x);
int fy=find(a[l].y);
if(fx!=fy)
{
f[fx]=fy;
dfs(x,l+1,sum+1);
f[fx]=fx;
}
dfs(x,l+1,sum);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].l);
}
for(int i=1;i<=n;i++)
f[i]=i;
sort(a+1,a+m+1);
int tot=0,num=0;
for(int i=1;i<=m;i++)
{
if(a[i].l!=a[i-1].l) b[++tot].l=i,b[tot-1].r=i-1;
int fx=find(a[i].x);
int fy=find(a[i].y);
if(fx!=fy)
{
f[fx]=fy;
num++;
b[tot].cnt++;
}
}
b[tot].r=m;//防止最后几个相等，r不赋值
if(num!=n-1)
{
printf("0
");
return 0;
}
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=tot;i++)
{
res=0;
dfs(i,b[i].l,0);
ans=ans*res%mo;
for(int j=b[i].l;j<=b[i].r;j++)
{
int fx=find(a[j].x);
int fy=find(a[j].y);
if(fx!=fy)
f[fx]=fy;
}
}
printf("%lld
",ans);
return 0;
}
/*1.不同的最小生成树中,每种权值的边出现的个数是确定的
2.不同的生成树中,某一种权值的边连接完成后,形成的联通块状态是一样的*/
8.汉堡店
做法：和次小生成树类似，先按最小生成树建边，枚举边加进来构成环，删掉最大边即可。如果（a,b）本身就在生成树中，也无伤大雅。
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<queue>
#include<map>
using namespace std;
const int maxm=1e6+7;
struct node
{
int x,y;
double l;
bool operator < (const node &s) const
{
return l<s.l;
}
}a[maxm];
int n,tot;
double ans,maxx[1007][21],cnt;
double w[1007];
double x[1007],y[1007],len[2007];
int f[1007],l;
bool vis[1007];
int pre[2007],last[1007],other[2007];
int jump[1007][21],dep[1007];
priority_queue<pair<double ,int> >q;
double dis1(int i,int j)
{
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
int find(int x)
{
if(x!=f[x])
f[x]=find(f[x]);
return f[x];
}
void add(int x,int y,double z)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
len[l]=z;
}
void dfs(int x)
{
for(int p=last[x];p;p=pre[p])
{
int v=other[p];
if(v==jump[x][0]) continue;
jump[v][0]=x;
dep[v]=dep[x]+1;
maxx[v][0]=len[p];
dfs(v);
}
}
double lca(int x,int y)
{
double ans=0;
if(dep[x]<dep[y]) swap(x,y);
for(int j=0;j<=19;j++)
{
if((dep[x]-dep[y])&(1<<j))
ans=max(ans,maxx[x][j]),x=jump[x][j];
}
if(x==y) return ans;
for(int j=19;j>=0;j--)
{
if(jump[x][j]!=jump[y][j])
{
ans=max(ans,maxx[x][j]);
ans=max(ans,maxx[y][j]);
x=jump[x][j];
y=jump[y][j];
}
}
return max(ans,max(maxx[x][0],maxx[y][0]));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",x+i,y+i,w+i);
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
a[++tot].x=i;
a[tot].y=j;
a[tot].l=dis1(i,j);
}
}
for(int i=1;i<=n;i++)
f[i]=i;
sort(a+1,a+tot+1);
for(int i=1;i<=tot;i++)
{
int fx=find(a[i].x);
int fy=find(a[i].y);
if(fx!=fy)
{
f[fx]=fy;
cnt+=a[i].l;
add(a[i].x,a[i].y,a[i].l);
add(a[i].y,a[i].x,a[i].l);
}
}
dfs(1);
for(int j=1;j<=19;j++)
{
for(int i=1;i<=n;i++)
{
jump[i][j]=jump[jump[i][j-1]][j-1];
maxx[i][j]=max(maxx[i][j-1],maxx[jump[i][j-1]][j-1]);
}
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
double ans1=lca(i,j);
ans=max(ans,(w[i]+w[j])/(cnt-ans1));
}
printf("%.2lf
",ans);
return 0;
}