一、算法部分
a.Prim算法 （从点的角度出发，选这n个点连接的边中最小的边） 稠密图 神似Dijkstra算法
priority_queue<node> q; //优先队列
Prim（s）{
memset(dis,0x7fffffff,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[s]=0;
q.push({0,s});
while(!q.empty()){
node n=q.top();
q.pop();
if(vis[n.pos]) continue;
vis[n.pos]=1;
count++;
ans+=n.dis;
for(int i=head[n.pos];i;i=nxt[i]){
int temp=edge[i].to;
if(dis[temp]>edge[i].weight){
dis[temp]=edge[i].weight;
q.push({dis[temp],temp);
}
}
if(count==n) cout<<ans<<endl;
}
b.kruskal算法 （从边的角度，将边排序） 目前感觉用的最多
for(int i=1;i<=n;i++) fa[i]=i;
sort(edge,edge+m,com);
int find(int x){
while(x!=fa[x])x=fa[x];
return x;
}
void kruskal(){
for(int i=0;i<m;i++){
int eu=find(edge[i].u);
int ev=find(edge[i].v);
if(eu==ev)continue;
fa[ev]=eu; //////////////////////////////////并查集(就一个数组的事？？？？？？)/////////////////////////////////////////////
total++;
ans+=edge[i].w;
if(total==n-1) break;}
}
二、习题
a.火车运输 难度：七颗星（因为我不会LCA。。。。。。。。。。。。。。。。。）
题目描述
A 国有 nnn 座城市，编号从 11 1 到 n nn，城市之间有 mmm 条双向道路。每一条道路对车辆都有重量限制，简称限重。
现在有 qqq 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式
第一行有两个用一个空格隔开的整数 n,m n,mn,m，表示 AAA 国有 n nn 座城市和 mmm 条道路。
接下来 mmm 行每行三个整数 x,y,zx, y, zx,y,z，每两个整数之间用一个空格隔开，表示从 xx x 号城市到 y y y 号城市有一条限重为 zzz 的道路。
注意： x≠yx
eq yx�=y，两座城市之间可能有多条道路 。
接下来一行有一个整数 qqq，表示有 qqq 辆货车需要运货。
接下来 qqq 行，每行两个整数 x,yx,yx,y，之间用一个空格隔开，表示一辆货车需要从 xxx 城市运输货物到 yyy 城市，保证 x≠yx eq yx�=y
输出格式
共有 qqq 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。
如果货车不能到达目的地，输出 −1-1−1。
输入输出样例
4 3 1 2 4 2 3 3 3 1 1 3 1 3 1 4 1 3
3 -1 3
说明/提示
对于 30%30\%30% 的数据，1≤n<10001 le n < 10001≤n<1000，1≤m<10,0001 le m < 10,0001≤m<10,000，1≤q<10001le q< 10001≤q<1000；
对于 60%60\%60% 的数据，1≤n<10001 le n < 10001≤n<1000，1≤m<5×1041 le m < 5 imes 10^41≤m<5×104，1≤q<10001 le q< 10001≤q<1000；
对于 100%100\%100% 的数据，1≤n<1041 le n < 10^41≤n<104，1≤m<5×1041 le m < 5 imes 10^41≤m<5×104，1≤q<3×1041 le q< 3 imes 10^4 1≤q<3×104，0≤z≤1050 le z le 10^50≤z≤105。
思路：先构造最大生成树，在利用LCA算法求最小值（后半句话还没弄懂）
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
int q;
int x,y;
int fa[10005][21],w[10005][21];
int f[10005];
int total;
struct node{
int u,v;
int w;
}edge[50005];
struct point{
int to;
int weight;
int nxt;
}ep[100005];
int head[10005];
int cnt;
bool vis[10002];
int deep[10005];
bool com(node a,node b){
return a.w >b.w ;
}
int find(int x){
while(x!=f[x])x=f[x];
return x;
}
void addedge(int x,int y,int z){
cnt++;
ep[cnt].to =y;
ep[cnt].weight =z;
ep[cnt].nxt =head[x];
head[x]=cnt;
}
void kruskal(){
sort(edge,edge+m,com);
for(int i=0;i<m;i++){
int eu=find(edge[i].u );
int ev=find(edge[i].v );
if(eu==ev)continue;
f[ev]=eu;
addedge(edge[i].u ,edge[i].v ,edge[i].w );
addedge(edge[i].v ,edge[i].u ,edge[i].w );
}
}
void dfs(int x){
vis[x]=1;
for(int i=head[x];i;i=ep[i].nxt){
int t=ep[i].to ;
if(vis[t])continue;
deep[t]=deep[x]+1;
fa[t][0]=x;
w[t][0]=ep[i].weight ;
dfs(t);
}
}
int lca(int x,int y){
if(find(x)!=find(y)) return -1;
int ans=0x7fffffff;
if(deep[x]>deep[y])swap(x,y);
for(int i=20;i>=0;i--){
if(deep[fa[y][i]]>=deep[x]){
ans=min(ans,w[y][i]);
y=fa[y][i];
}
}
if(x==y) return ans;
for(int i=20;i>=0;i--){
if(fa[x][i]!=fa[y][i]){
ans=min(ans,min(w[x][i],w[y][i]));
x=fa[x][i];
y=fa[y][i];
}
}
ans=min(ans,min(w[x][0],w[y][0]));
return ans;
}
int main(){
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>edge[i].u >>edge[i].v >>edge[i].w ;
}
for(int i=1;i<=n;i++) f[i]=i;
kruskal();
for(int i=1;i<=n;i++){
if(!vis[i]){
deep[i]=1;
dfs(i);
fa[i][0]=i;
w[i][0]=0x7fffffff;
}
}
for(int i=1;i<=20;i++){
for(int j=1;j<=n;j++){
fa[j][i]=fa[fa[j][i-1]][i-1];
w[j][i]=min(w[j][i-1],w[fa[j][i-1]][i-1]);
}
}
cin>>q;
for(int i=1;i<=q;i++){
cin>>x>>y;
cout<<lca(x,y)<<endl;
}
}
三、出题 总结
1、如果有出发点和终点，那大部分应该选prim算法。
2、大部分会在n-k，k条边停止。
3、可能给点坐标会 自己建完全图，构造最大生成树。