题意：裸最小生成树，主要是要按照字典序。
思路：模板
prim：
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define INF 0x7fffffff #define MAXN 128 bool vis[MAXN]; int lowu[MAXN];//记录起始边（已加入集合中的边） int lowc[MAXN]; struct Edge{ int u,v; }; Edge ans[MAXN*MAXN]; int cnt;//边数 bool cmp(Edge a,Edge b){ if(a.u!=b.u)return a.u<b.u; return a.v<b.v; } bool prim(int cost[][MAXN],int n){//标号从0开始 int i,j,minc,p; memset(vis,false,sizeof(vis)); vis[0]=true; for(i=1;i<n;++i){ lowu[i]=0;//起始边都为0 lowc[i]=cost[0][i]; } for(i=1;i<n;++i){ minc=INF; p=-1; for(j=0;j<n;++j) if(!vis[j]&&(lowc[j]<minc||(lowc[j]==minc&&lowu[j]<p))){//字典序 minc=lowc[j]; p=j; } if(minc==INF)return false;//原图不连通 if(lowu[p]<p){ ans[cnt].u=lowu[p]+1; ans[cnt++].v=p+1; } else{ ans[cnt].u=p+1; ans[cnt++].v=lowu[p]+1; } vis[p]=true; for(j=0;j<n;++j) if(!vis[j]&&(cost[p][j]<lowc[j]||(cost[p][j]==lowc[j]&&p<lowu[j]))){//字典序 lowu[j]=p;//起始边变为p lowc[j]=cost[p][j]; } } return true; } int main(){ int t; int n,m,a,b,w,i,j; int cost[MAXN][MAXN]; scanf("%d",&t); while(t--){ scanf("%d",&n); //m=n*(n-1)/2;//m边条数 for(i=0;i<n;++i) for(j=0;j<n;++j){ scanf("%d",&w); if(w==0)w=INF; cost[i][j]=w; } cnt=0; if(prim(cost,n)){ sort(ans,ans+cnt,cmp);//字典序 for(i=0;i<cnt-1;++i) printf("%d %d ",ans[i].u,ans[i].v); printf("%d %d ",ans[i].u,ans[i].v); } else printf("-1 "); } return 0; }
kruskal：注意sort排序是不稳定排序，那么cmp中的w相同时怎么排要指出。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; #define MAXN 110//最大点数 #define MAXM 10000//最大边数 int F[MAXN];//并查集使用 struct Edge{ int u,v,w; }edge[MAXM];//存储边的信息，包括起点/终点/权值 int tol;//边数，加边前赋值为0 int cnt;//计算加入的边数 Edge ans[MAXM];//存储结果 void addedge(int u,int v,int w){ edge[tol].u=u; edge[tol].v=v; edge[tol++].w=w; } //排序函数，将边按照权值从小到大排序 bool cmp(Edge a,Edge b){//sort排序不稳定 if(a.w!=b.w)return a.w<b.w; if(a.u!=b.u)return a.u<b.u; return a.v<b.v; } bool cmp2(Edge a,Edge b){ if(a.u!=b.u)return a.u<b.u; return a.v<b.v; } int find(int x){ if(F[x]==-1)return x; return F[x]=find(F[x]); } //传入点数，返回最小生成树的权值，如果不连通返回-1 void kruskal(int n){ memset(F,-1,sizeof(F)); sort(edge,edge+tol,cmp); int i,u,v,w,t1,t2; for(i=0;i<tol;++i){ u=edge[i].u; v=edge[i].v; w=edge[i].w; t1=find(u); t2=find(v); if(t1!=t2){ ans[cnt++]=edge[i]; F[t1]=t2; } if(cnt==n-1)break; } // if(cnt<n-1)return -1;//不连通 // return ans; } int main(){ int t; int n,m,a,b,w,i,j; scanf("%d",&t); while(t--){ scanf("%d",&n); //m=n*(n-1)/2;//m边条数 tol=0;cnt=0; for(i=1;i<=n;++i) for(j=1;j<=n;++j){ scanf("%d",&w); if(j<=i)continue; if(w==0)continue; addedge(i,j,w); } kruskal(n); if(cnt!=n-1)printf("-1 "); else{ sort(ans,ans+cnt,cmp2);//此处控制输出排序 for(i=0;i<cnt-1;++i) printf("%d %d ",ans[i].u,ans[i].v); printf("%d %d ",ans[i].u,ans[i].v); } } return 0; }