博客

公路村村通

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:

输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:

输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例:

6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出样例:

12

【解题思路】：这是一道标准的求图的最小生成树的题目，我这里建图采用了邻接链表的方式，因为一幕有内存限制，用邻接矩阵会被卡内存，所以用了邻接链表（边表也可以，大家可以试试）

求最小生成树我采用了普利姆算法，普利姆算法可以作用的前提是图得是联通图，算法描述：

设G=(V,E）是连通图，TE是G最小支撑树边的集合。

1.算法开始时，

2.找到满足

的边（u，v），把它并入集合TE中，同时v并入U。

3.反复执行2，直到U=V时结束算法。

普利姆算法是在保证图联通的前提下每次取权值最小的边加入集合U中，最后全部的点都在树中，就得到了最小生成树。

#include<iostream>
#define maxsize 3005
#include<queue>
using namespace std;
const int MAX=9999;
typedef struct Edge{//边结点的结构体 
	int VerAdj;//邻接顶点的序号，用自然数编号 
	int cost;//边的权值 
	struct Edge* link;//指向下一个边结点的指针 
}Edge;
typedef struct Vertex{//顶点表中的结点的结构体 
	int VerName;//顶点的名称 
	Edge* adjacent;//边链表头指针 
}Vertex; 
 struct Graph{
	Vertex Head[maxsize];
	int numEdges,Graphsize;
}G;
int lowcost[maxsize],vex[maxsize],visited[maxsize];


void Prim_method(struct Graph G){//普利姆算法（邻接表存储） 
	int i,j,k,n=G.Graphsize;
	int max=9999,ldist,u,v;
	Edge *p;
	for(i=1;i<=n;i++){//初始化 
		lowcost[i]=max;
		visited[i]=0;//visited记录点i是否在最小支撑树中 
		vex[i]=-1; //vex[i]是i的前驱结点 
	}
	visited[1]=1;lowcost[1]=0;
	for(p=G.Head[1].adjacent;p;p=p->link){//先将第一个点的邻接点访问 
		k=p->VerAdj;
		lowcost[k]=p->cost;
		vex[k]=1;
	}
	for(j=1;j<n;j++){
		ldist=max;  //确定轻边 
		for(i=1;i<=n;i++){
			if(lowcost[i]<ldist&&visited[i]==0){
				ldist=lowcost[i];
				u=i;
			}
		}
		visited[u]=1;
		for(p=G.Head[u].adjacent;p;p=p->link){
			v=p->VerAdj;
			if(p->cost<lowcost[v]&&visited[v]==0){
				lowcost[v]=p->cost;vex[v]=u;
			}
		}
	}
}
int N,M;
void create_graph(struct Graph& G){
	int i,j,k;
	int v1,v2,Cost;
	Edge *p,*r;
	scanf("%d %d",&N,&M);
    if(M<N-1) return;
	G.Graphsize=N;
	G.numEdges=M;
    for(i=1;i<=G.Graphsize;i++){
    	G.Head[i].VerName=i;
    	G.Head[i].adjacent=NULL;
	}
	
	for(k=1;k<=G.numEdges;k++){
		scanf("%d %d %d",&v1,&v2,&Cost);
		p=new Edge;
		p->VerAdj=v2;
		p->cost=Cost;
		p->link=NULL;
		Edge *q=G.Head[v1].adjacent;
		if(q==NULL) G.Head[v1].adjacent=p;
		else{
			while(q->link!=NULL){
				q=q->link;
			}
			q->link=p;
		}
		r=new Edge;
		r->VerAdj=v1;
		r->cost=Cost;
		r->link=NULL;
		Edge* r0=G.Head[v2].adjacent;
		if(r0==NULL) G.Head[v2].adjacent=r;
		else{
			while(r0->link!=NULL)
			   r0=r0->link;
			r0->link=r;
		}
	}
}
int main(){
	int sum=0;
	create_graph(G);
	Prim_method2(G);
    if(N>M){
        cout<<"-1";
        return 0;
    }
    
	for(int i=1;i<=N;i++){
		sum+=lowcost[i];
	}
    if(sum>MAX){
         cout<<"-1";
        return 0;
    }
	cout<<sum;
} 

这里在建图时要注意，邻接链表Edge结点连接一次只建立了一条有向路，需要将一条路连两次才能创建无向图。

关于题目中说道的数据不足难以保证畅通，有几种情况：

M<N-1，不能把每个点连起来，自然不能形成连通图。

M>=N-1，但是图不连通，这种情况下，数组lowcost一开始初始化为9999（即为无穷），所以最后sum加和时只需要判断是不是比MAX大即可知道图是否联通。