浙大计算机研究生复试上机考试-2007年_Prim_Kruskal_hdoj1863
发布时间
阅读量：
阅读量
http://acm.hdu.edu.cn/showproblem.php?pid=1863
//Problem : 1863 ( 畅通工程 ) Judge Status : Accepted
//RunId : 19221043 Language : G++ Author : 311309030328
//Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=110;
int pre[MAXN];
struct node
{
int u,v,val;
}edge[MAXN];//结构体数组
int cmp(node x, node y)
{
return x.val<y.val;//升序
}
int find(int x)
{
if(pre[x]==x)
{
return x;
}
return pre[x]=find(pre[x]);
}
int main()
{
int m,n;
while(~scanf("%d%d",&m,&n),m)
{
int i,j,a,b,c;
//memeset(pre,0,sizoef(pre))
for(i=1;i<=n;i++)
{
pre[i]=i;//init()
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].val);
}
sort(edge+1,edge+m+1,cmp);//默认升序
int sum=0;
for(i=1;i<=m;i++)
{
int fx=find(edge[i].u);
int fy=find(edge[i].v);
if(fx!=fy)
{
pre[fy]=fx;
sum+=edge[i].val;
}
}
int cnt=0;
for(i=1;i<=n;i++)
{
if(pre[i]==i)
{
cnt++;
}
}
if(cnt==1)
{
printf("%d\n",sum);
}
else
{
printf("?\n");
}
}
return 0;
}
/*
Problem : 1863 ( 畅通工程 ) Judge Status : Accepted
RunId : 19220622 Language : G++ Author : 311309030328
Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta
#include<cstdio>
#include<algorithm>
86. #define MAXN 110
#define INF 0xffff
89. int edge[MAXN][MAXN];
int visit[MAXN];
int lowcost[MAXN];
int n;
int Prim()
{
int i,j,k;
int sum=0;
int min;
for(i=1;i<=n;i++)
{
lowcost[i]=edge[i][1];
visit[i]=0;
}
for(i=1;i<=n;i++)
{
min=INF;
for(j=1;j<=n;j++)
{
if(!visit[j] && lowcost[j]<min)
{
min=lowcost[j];
k=j;
}
}
if(min==INF)
{
return -1;
}
visit[k]=1;
sum+=min;
for(j=1;j<=n;j++)
{
if(!visit[j] && lowcost[j]>edge[k][j])
{
lowcost[j]=edge[k][j];
}
}
}
return sum;
}
131. int main()
{
int m;
while(~scanf("%d%d",&m,&n),m)
{
int i,j,a,b,c;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
edge[i][j]=0;
else
edge[i][j]=edge[j][i]=INF;
}
}
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(edge[a][b]>c)
{
edge[a][b]=edge[b][a]=c;
}
}
int temp=Prim();
if(temp!=-1)
{
printf("%d\n",temp);
}
else
{
printf("?\n");
}
}
return 0;
}
*/
代码解释全部评论 (0)
还没有任何评论哟~