HDU 1233 还是畅通工程（最小生成树）

HDU 1233 还是畅通工程（最小生成树）

还是畅通工程

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 37570    Accepted Submission(s): 16923

Problem Description

某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

Input

测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( < 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。

Output

对每个测试用例，在1行里输出最小的公路总长度。

Sample Input

3 1 2 1 1 3 2 2 3 4 4 1 2 1 1 3 4 1 4 1 2 3 3 2 4 2 3 4 5 0

Sample Output

3 5

Hint

Hint

Huge input, scanf is recommended.

Source

题意：就是给一个图，要求连通每个村庄的最短公路，典型的最小生成树。

给个TLE代码....:

#include#include#include#include#include#include#include#include#include#includetypedef long long LL;using namespace std;#define MIN 65535#define MAX_Point 120 //最大顶点数 #define MAX_Edge 14400 //最大的边数 int flag1 =0;double sum;double arr_list[MAX_Point][MAX_Point]; struct Edge{ int point; double lowcost; int flag;};Edge edge[MAX_Edge];double prim(int n){ int i,j,k=1,flag; double min,sum2=0; j=1; for(i=1;i<=n;i++) { if(i!=j) { edge[i].point=i; edge[i].lowcost=arr_list[j][i]; edge[i].flag=0; } } edge[j].lowcost=0; edge[j].flag=1; for(i=2;i<=n;i++) { k=1; min=MIN; flag=0; for(j=2;j<=n;j++) { if(edge[j].flag==0 && edge[j].lowcost>m) { if(m==0) break; sum=0; for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) arr_list[i][j]=65535; for(int i=1;i<=m*(m-1)/2;i++) { cin>>a>>b>>time_data; if(time_data

多姿势AC代码：

#include#include#include#include#include#define N 110#define INF 0x7ffffffusing namespace std;int n;int dist[N],map[N][N],isvisited[N];int prim(){ int i,j,min,pos; int sum=0; memset(isvisited,false,sizeof(isvisited)); //初始化 for(i=1;i<=n;i++){ dist[i]=map[1][i]; } //从1开始 isvisited[1]=true; dist[1]=65535; //找到权值最小点并记录下位置 for(i=1;imap[pos][j]){ dist[j]=map[pos][j]; } } } return sum;}int main(){ while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=INF; int m=n*(n-1)/2; for(int i=0;it) map[u][v]=map[v][u]=t; } cout<

AC代码：

#include#include#include#include#include#define N 110#define INF 0x7ffffffusing namespace std;int v[N],d[N],mp[N][N],n;int prim(){ for(int i=1;i<=n;i++) { d[i]=INF,v[i]=0; } d[1]=0; for(int i=0;id[j]) mmin=d[t=j]; } v[t]=1; for(int j=1;j<=n;j++) { if(!v[j]) d[j]=min(d[j],mp[t][j]); } } int ans=0; for(int i=1;i<=n;i++) ans+=d[i]; return ans;}int main(){ while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) mp[i][j]=INF; int m=n*(n-1)/2; for(int i=0;it) mp[u][v]=mp[v][u]=t; } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。