先简单说一下，生成最小树一般常用两种算法，一种是prim另一种是kruskal，两种算法也各有利弊，比如说prim编程比较复杂一些而kruskal编程则相对容易一些，但是时间复杂度却差了些。
prim跟dijkstra差不多，简单来说prim适合稠密图，而kurskal则适合稀疏图。
文章目录
1.POJ - 1251(生成最小树模板题)
这个题也就是把字母转换成数字，直接套用模板即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v,w;
}edge[maxn];
int f[maxn];
int ans=0,k=0;
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void kruskal(){
ans=0;
sort(edge,edge+k,rule());
for(int i=0;i<k;i++){
int dx=ifind(edge[i].u);
int dy=ifind(edge[i].v);
if(dx==dy) continue;
f[dx]=dy;
ans+=edge[i].w;
}
}
int main()
{
int n;
while(cin>>n&&n){
for(int i=0;i<30;i++) f[i]=i;
int w,m;
k=0;
char x,y;
for(int i=0;i<n-1;i++){
cin>>x>>m;
for(int j=0;j<m;j++){
cin>>y>>w;
edge[k].u=(int)(x-'A');
edge[k].v=(int)(y-'A');
edge[k++].w=w;
}
}
kruskal();
cout<<ans<<endl;
}
return 0;
}
2.POJ - 1287（模板题）
网友的翻译我是爱了。
是个稠密图应该用prim，但是我用了kruskal（好写）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1000000
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v,w;
}edge[maxn];
int f[maxn];
int n,m;
int ans=0;
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void kruskal(){
ans=0;
sort(edge,edge+m,rule());
for(int i=0;i<m;i++){
int dx=ifind(edge[i].u);
int dy=ifind(edge[i].v);
if(dx==dy) continue;
f[dx]=dy;
ans+=edge[i].w;
}
}
int main()
{
while(cin>>n&&n){
cin>>m;
for(int i=0;i<=n;i++) f[i]=i;
for(int i=0;i<m;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
}
kruskal();
cout<<ans<<endl;
}
return 0;
}
3.POJ 2031（生成最小树）
这个题注意一下他们之间的权值是怎么的来的就行了，也算是个板子题把
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 10010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v;
double w;
}edge[maxn];
struct ss{
double x,y,z,r;
}a[maxn];
int f[maxn];
int n,m;
double ans=0;
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void kruskal(){
ans=0;
sort(edge,edge+m,rule());
for(int i=0;i<m;i++){
int dx=ifind(edge[i].u);
int dy=ifind(edge[i].v);
if(dx==dy) continue;
f[dx]=dy;
ans+=edge[i].w;
}
}
double judge(ss a,ss b){
double temp=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z));
if(temp<=a.r+b.r) return 0;
return temp-a.r-b.r;
}
int main()
{
while(cin>>n&&n){
m=0;
for(int i=0;i<maxn;i++) f[i]=i;
for(int i=0;i<n;i++){
scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r);
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
edge[m].u=i;
edge[m].v=j;
edge[m++].w=judge(a[i],a[j]);
}
}
kruskal();
printf("%.3f\n",ans);
}
return 0;
}
4. POJ-2421
这个题有些边已经连接起来了，所以我们提前把他连好的边加到树里就可以了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1000000
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v,w;
}edge[maxn];
int f[maxn];
int n,m,k;
int ans=0;
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void kruskal(){
ans=0;
sort(edge,edge+k,rule());
for(int i=0;i<k;i++){
int dx=ifind(edge[i].u);
int dy=ifind(edge[i].v);
if(dx==dy) continue;
f[dx]=dy;
ans+=edge[i].w;
}
}
int main()
{
cin>>n;
for(int i=0;i<=n;i++) f[i]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int x;
scanf("%d",&x);
if(i==j) continue;
edge[k].u=i;
edge[k].v=j;
edge[k++].w=x;
}
}
cin>>m;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
int dx=ifind(x);
int dy=ifind(y);
if(dx==dy) continue;
f[dx]=dy;
}
kruskal();
cout<<ans<<endl;
return 0;
}
5.ZOJ - 1586（模板题）
这个题与模板题不同的一点是，每个点都有自己的花费，假设链接a b两点，则权值为ab两点之间的权值+a的花费+b的花费
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
int a[maxn],f[maxn];
struct wazxy{
int u,v,w;
}e[maxn*maxn];
int n,k;
int ans=0;
struct rule{
bool operator ()(const wazxy & a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
return f[x]=ifind(f[x]);
}
void kruskal(){
sort(e,e+k,rule());
for(int i=0;i<k;i++){
int dx=ifind(e[i].u);
int dy=ifind(e[i].v);
if(dx==dy) continue;
else{
ans+=e[i].w;
f[dx]=dy;
}
}
}
int main()
{
int t;
cin>>t;
while(t--){
for(int i=0;i<maxn;i++) f[i]=i;
ans=0,k=0;
cin>>n;
int x;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&x);
if(i==j) continue;
e[k].u=i;
e[k].v=j;
e[k++].w=x+a[i]+a[j];
}
}
//for(int i=0;i<k;i++) cout<<e[i].w<<" ";
kruskal();
cout<<ans<<endl;
}
return 0;
}
6.POJ - 1789
把每个字符串看成一个点，每个点之间的权值就是他们对应不同的字符个数
这个题练习了一下prim算法，毕竟是个稠密图
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 2010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
int n;
string s[maxn];
int maps[maxn][maxn];
int dis[maxn];
bool visited[maxn];
int dif(int x,int y){
int ans=0;
for(int i=0;i<7;i++){
if(s[x][i]!=s[y][i]) ans++;
}
return ans;
}
struct node{
int id,dis;
node(int a,int b){id=a,dis=b;}
bool operator < (const node & a)const
{return dis>a.dis;}
};
int prim(){
int ans=0;
memset(dis,MaxN,sizeof(dis));
priority_queue<node> q;
dis[1]=0;
q.push(node(1,0));
while(!q.empty()){
node temp=q.top();
q.pop();
int now=temp.id;
if(visited[now]) continue;
visited[now]=true;
ans+=dis[now];
for(int i=1;i<=n;i++){
if(i==now) continue;
int val=maps[now][i];
if(!visited[i]&&dis[i]>val){
dis[i]=val;
q.push(node(i,dis[i]));
}
}
}
return ans;
}
int main()
{
while(cin>>n&&n){
memset(visited,false,sizeof(visited));
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++){
for(int f=1;f<=n;f++){
if(i==f) continue ;
maps[i][f]=dif(i,f);
}
}
cout<<"The highest possible quality is 1/"<<prim()<<"."<<endl;
}
}
7.POJ - 2349（生成最小树中的最大的边权）
题意：给你n个点的二维坐标，求生成最小树中到数第k大的边权为多少
拿一个数组来记录一下边，然后sort一下输出即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 510
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v;
double w;
}edge[maxn*maxn];
int f[maxn];
double b[maxn];
int n,m,k,cnt,cnt1;
double ans=0;
struct node{
double x,y;
}a[maxn];
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void kruskal(){
ans=0;
sort(edge,edge+cnt,rule());
for(int i=0;i<cnt;i++){
int dx=ifind(edge[i].u);
int dy=ifind(edge[i].v);
if(dx==dy) continue;
f[dx]=dy;
ans+=edge[i].w;
b[cnt1++]=edge[i].w;
}
}
double dis(int x, int y){
return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
int main()
{
int t;
cin>>t;
while(t--){
for(int i=0;i<maxn;i++) f[i]=i;
cnt=0,cnt1=0;
cin>>k>>m;
for(int i=1;i<=m;i++) cin>>a[i].x>>a[i].y;
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
if(i==j) continue ;
edge[cnt].u=i;
edge[cnt].v=j;
edge[cnt++].w=dis(i,j);
}
}
kruskal();
sort(b,b+cnt1);
printf("%.2f\n",b[cnt1-k]);
}
return 0;
}
8.POJ - 1751
天啦噜，这个题前期tle都tle到天上了，建议G++提交（我也不知道为什么）
存边的时候注意一下存一次就够了不要重了，不然带来的就是tle
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1010
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v;
double w;
}edge[maxn*maxn];
int f[maxn];
double b[maxn];
int n,m,k,cnt;
double ans=0;
struct node{
double x,y;
}a[maxn];
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void kruskal(){
sort(edge,edge+cnt,rule());
for(int i=0;i<cnt;i++){
int dx=ifind(edge[i].u);
int dy=ifind(edge[i].v);
if(dx==dy) continue;
f[dx]=dy;
printf("%d %d\n",edge[i].u,edge[i].v);
}
}
inline double dis(int x, int y){
return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
int main()
{
for(int i=0;i<maxn;i++) f[i]=i;
cnt=0;
cin>>m;
for(int i=1;i<=m;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
for(int i=1;i<=m;i++){
for(int j=i+1;j<=m;j++){
edge[cnt].u=i;
edge[cnt].v=j;
edge[cnt++].w=dis(i,j);
}
}
cin>>m;
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
int dx=ifind(x);
int dy=ifind(y);
if(dx==dy) continue ;
f[dx]=dy;
}
kruskal();
return 0;
}
9.POJ-1258（模板题）
模板模板模板
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 110
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v;
int w;
}edge[maxn*maxn];
int f[maxn];
int n,m,k,cnt;
int ans=0;
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void kruskal(){
sort(edge,edge+cnt,rule());
ans=0;
for(int i=0;i<cnt;i++){
int dx=ifind(edge[i].u);
int dy=ifind(edge[i].v);
if(dx==dy) continue;
f[dx]=dy;
ans+=edge[i].w;
}
}
int main()
{
while(cin>>m){
for(int i=0;i<maxn;i++) f[i]=i;
cnt=0;
for(int i=1;i<=m;i++){
for(int j=1;j<=m;j++){
int x;
scanf("%d",&x);
if(i<=j) continue;
edge[cnt].u=i;
edge[cnt].v=j;
edge[cnt++].w=x;
}
}
kruskal();
cout<<ans<<endl;
}
return 0;
}
10.HDU1233（模板题）
这个之前写过
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#define maxn 110
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int f[maxn];
struct wazxy{
int u,v,w;
}a[maxn*maxn];
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
struct rule{
bool operator()(const wazxy & a,const wazxy & b){
return a.w<b.w;
}
};
int main()
{
int n;
while(cin>>n&&n){
int m=n*(n-1)/2;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
}
sort(a+1,a+m+1,rule());
int ans=0;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++){
int dx=ifind(a[i].u);
int dy=ifind(a[i].v);
if(dx==dy) continue;
f[dx]=dy;
ans+=a[i].w;
}
cout<<ans<<endl;
}
return 0;
}
11.HDU-1301
ps跟第一题一样的
12.HDU-1875
这个题注意判断一下哪些边不可取即可，这里我是在存图的时候判断的边长度是否符合题意，不符合就不加入。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 110
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v;
double w;
}edge[maxn*maxn];
int f[maxn];
bool visited[maxn];
int n,m,k,cnt;
double ans=0;
struct node{
double x,y;
}a[maxn];
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void init(){
for(int i=0;i<maxn;i++) f[i]=i;
memset(visited,false,sizeof(visited));
cnt=0,ans=0;
}
double dis(int x,int y){
double temp=(a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y);
temp=sqrt(temp);
if(temp>1000||temp<10) return -1;
return temp;
}
void kruskal(){
sort(edge,edge+cnt,rule());
for(int i=0;i<cnt;i++){
int dx=ifind(edge[i].u);
int dy=ifind(edge[i].v);
if(dx==dy) continue;
ans+=edge[i].w;
visited[edge[i].u]=true;
visited[edge[i].v]=true;
f[dx]=dy;
}
}
int main()
{
int t;
cin>>t;
while(t--){
init();
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
double temp=dis(i,j);
if(temp==-1) continue;
edge[cnt].u=i;
edge[cnt].v=j;
edge[cnt++].w=dis(i,j);
}
}
kruskal();
bool flag=true;
for(int i=1;i<=n;i++){
if(!visited[i]) flag=false;
//cout<<visited[i]<<endl;
}
if(flag==false) cout<<"oh!"<<endl;
else printf("%.1f\n",ans*100);
}
return 0;
}
13.POJ-3026（bfs+kruskal）
这个题说难吧，他不难，就是挺麻烦的。
这个题先给你些许个点，每个点的距离需要你自己bfs计算出来。
我做这个题的时候出了好多bug，但是都是小问题，很快就调好了
注意：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 510
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int u,v;
int w;
}edge[maxn*maxn];
char s[maxn];
int n,m,num,rem,cnt,ans;
int a[maxn][maxn],f[maxn];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
bool visited[maxn][maxn];
struct node{
int x,y,steps;
node(int a,int b,int c){x=a,y=b,steps=c;}
};
struct rule{
bool operator()(const wazxy &a,const wazxy & b){
return a.w<b.w;
}
};
int ifind(int x){
if(x==f[x]) return x;
else return f[x]=ifind(f[x]);
}
void init(){
memset(a,-1,sizeof(a));
for(int i=0;i<maxn;i++) f[i]=i;
num=1,cnt=0;
}
void bfs(int x,int y){
queue<node> q;
visited[x][y]=true;
q.push(node(x,y,0));
while(!q.empty()){
node temp=q.front();
q.pop();
if(a[temp.x][temp.y]>0&&a[temp.x][temp.y]!=rem){
edge[cnt].u=rem;
edge[cnt].v=a[temp.x][temp.y];
edge[cnt++].w=temp.steps;
// cout<<a[temp.x][temp.y]<<endl;
}
for(int i=0;i<4;i++){
int nx=temp.x+dx[i],ny=temp.y+dy[i];
if(!visited[nx][ny]&&a[nx][ny]>=0){
visited[nx][ny]=true;
// cout<<nx<<" "<<ny<<endl;
q.push(node(nx,ny,temp.steps+1));
}
}
}
}
void kruskal(){
sort(edge,edge+cnt,rule());
ans=0;
for(int i=0;i<cnt;i++){
int xx=ifind(edge[i].u);
int yy=ifind(edge[i].v);
if(xx==yy) continue;
ans+=edge[i].w;
f[xx]=yy;
}
}
int main()
{
int t;
cin>>t;
while(t--){
int n,m;
init();
cin>>m>>n;
gets(s);
for(int i=1;i<=n;i++){
gets(s);
for(int j=0;j<m;j++){
if(s[j]==' ') a[i][j+1]=0;
else if(s[j]=='A'||s[j]=='S') a[i][j+1]=num++;
}
}
// for(int i=1;i<=n;i++){
// for(int j=1;j<=m;j++){
// cout<<a[i][j]<<" ";
// }
// cout<<endl;
// }
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]>0){
rem=a[i][j];
memset(visited,false,sizeof(visited));
bfs(i,j);
// cout<<"1"<<endl;
}
}
}
kruskal();
cout<<ans<<endl;
}
return 0;
}
京公网安备 11010502036488号