题意,在给出的图中,使用最小花费的边,使这个图仍然连通。
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int maxn=10005; int head[maxn]; int n,len=0,counter; long long ans; struct node{ int v,cost,u; //操作符的重写默认是小于等于 bool operator < (const node& tmp) const{ return cost< tmp.cost; } }gra[maxn]; struct BingCha{ //并查集 int father[105]; void initial(){ //初始化不要忘记 for(int i=1;i<=n;i++){ father[i]=i; } } int getfather(int v){ if(father[v]==v)return v; return father[v]=getfather(father[v]); //状态压缩 } bool findtwo(int a,int b){ //看是否是同根的 return getfather(a)==getfather(b); } void unioned(int a,int b){ int fa=father[a],fb=father[b]; father[fa]=fb; } }jihe; void addedge(int u,int v,int cost){ gra[len].u=u; gra[len].v=v; gra[len].cost=cost; len++; } void init(){ len=0; counter=1;ans=0; int x; memset(head,-1,sizeof(head)); //memset gra? for(int i=1;i<=n;i++){//add the edges for(int j=1;j<=n;j++){ scanf("%d",&x); if(i<j){ addedge(i,j,x); } } } } int main(){ while(scanf("%d",&n)!=EOF){ init(); sort(gra,gra+len); //已经有序,那么从小值开始选边添加即可,也保证了最优结果 int idx=0; jihe.initial(); while(counter<n || idx<len){ if(!jihe.findtwo(gra[idx].u,gra[idx].v)){ //如果不同根,就选择这条边,执行更新操作 ans+=gra[idx].cost; counter++; jihe.unioned(gra[idx].u,gra[idx].v); } idx++; } printf("%d\n",ans); } }
2421 也是裸的mst:只要把已经建了的作为输入先处理一下就好了。
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; ; int n,len,counter; long long ans; struct node{ int v,cost,u; bool operator < (const node& tmp) const{ return cost< tmp.cost; } }gra[maxn*(maxn-)>>]; struct BingCha{ ]; void initial(){ ;i<=n;i++){ father[i]=i; } } int getfather(int v){ if(father[v]==v)return v; return father[v]=getfather(father[v]); } bool findtwo(int a,int b){ return getfather(a)==getfather(b); } void unioned(int a,int b){ int fa=getfather(a),fb=getfather(b); father[fa]=fb; } }jihe; void addedge(int u,int v,int cost){ gra[len].u=u; gra[len].v=v; gra[len].cost=cost; len++; } int findxy(int x,int y){ if(x>y){int z=y;y=x;x=z;} ,id=; ;i<x;i++){ id+=j--; } y-=x;// here!!! id+=y; return id; } void init(){ len=; counter=;ans=; jihe.initial(); int x,q,y; //memset gra? ;i<=n;i++){//add the edges ;j<=n;j++){ scanf("%d",&x); if(i<j){ addedge(i,j,x); } } } scanf("%d",&q); ;i<=q;i++){ scanf("%d%d",&x,&y); ; if(!jihe.findtwo(gra[idx].u,gra[idx].v)){ counter++; jihe.unioned(gra[idx].u,gra[idx].v); } } } int main(){ while(scanf("%d",&n)!=EOF){ init(); sort(gra,gra+len); ; while(counter<n){//|| idx<=len if(!jihe.findtwo(gra[idx].u,gra[idx].v)){ ans+=gra[idx].cost; counter++; jihe.unioned(gra[idx].u,gra[idx].v); } idx++; } printf("%d\n",ans); } }