本文主要是介绍HDU 1102 Constructing Roads，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
这道题的要求是任意两个地点必须直接相连或者只通过一个地方间接相连。
所以合并a,b的时候，不只是把a和b并在一起，具体见UNION函数。
然后就是Kruskal算法求最小生成树就行了。
int N,Q;
//边
struct edge{int from,to;int value;void init(int from,int to,int value){this->from=from;this->to=to;this->value=value;}bool operator <(const edge&b)const{return value<b.value;}
}edges[5000];
int En;
//并查集+边表
struct ArcNode{//边链表 int number;ArcNode *next;ArcNode(int i,ArcNode* k):number(i),next(k){}
};
struct node{int parent;//用于并查集 ArcNode *next;//边链表：记录此节点连的边 void init(int i){parent=i;next=NULL;}
}nodes[110]; int find(int x){int r=x;while(r!=nodes[r].parent){r=nodes[r].parent;}return nodes[x].parent=r;
}
void Union(int a,int b){if(a==b) return;nodes[a].parent=b;
}
void UNION(int v1,int v2){//合并V1和v2 //找到v1,v2的根节点 int a=find(v1),b=find(v2);//将V1与 V2所连的节点相连 ArcNode* pArcNode=nodes[v2].next;while(pArcNode!=NULL){int c=find(pArcNode->number);Union(a,c);pArcNode=pArcNode->next;}//将V2与 V1所连的节点相连 pArcNode=nodes[v1].next;while(pArcNode!=NULL){int c=find(pArcNode->number);Union(a,c);pArcNode=pArcNode->next;}//将v1,v2加入对方的边链表 pArcNode=new ArcNode(v1,nodes[v2].next);nodes[v2].next=pArcNode;pArcNode=new ArcNode(v2,nodes[v1].next);nodes[v1].next=pArcNode;//联合v1,v2 Union(a,b);
}int dis[101][101];//记录距离 int main(void)
{while(scanf("%d",&N)!=EOF) { //读取距离for(int i=0;i<N;i++){for(int j=0;j<N;j++){scanf("%d",&dis[i][j]);}}//初始化 for(int i=0;i<N;i++) nodes[i].init(i);//根据已建边合并villagescin>>Q;for(int i=0;i<Q;i++){static int v1,v2;scanf("%d%d",&v1,&v2);UNION(v1-1,v2-1);}//建边En=0;for(int i=0;i<N;i++){for(int j=i+1;j<N;j++){int a=find(i),b=find(j);if(a!=b) edges[En++].init(i,j,dis[i][j]);}}//计算（Kruskal算法）int ANS=0; sort(edges,edges+En);//排序 for(int i=0;i<En;i++){int a=find(edges[i].from),b=find(edges[i].to);if(a==b) continue;UNION(edges[i].from,edges[i].to);ANS+=edges[i].value;}cout<<ANS<<endl;//释放new所申请的内存 for(int i=0;i<N;i++){ArcNode* pArcNode=nodes[i].next;while(pArcNode!=NULL){ArcNode* temp=pArcNode;pArcNode=pArcNode->next;delete temp;}} }return 0;
}这篇关于HDU 1102 Constructing Roads的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
