最小生成树有关问题【PAT】
最小生成树问题【PAT】
8-06. 畅通工程之局部最小花费问题
时间限制
10 ms
内存限制
32000 kB
代码长度限制
8000 B
判题程序
Standard
某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建快速路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全地区畅通需要的最低成本。
输入格式说明：
输入的第1行给出村庄数目N (1<=N<=100)；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态：每行给出4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以及修建状态 — 1表示已建，0表示未建。
输出格式说明：
输出全省畅通需要的最低成本。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 |
3 1 2 1 0 1 3 2 0 2 3 4 0 |
3 |
| 2 |
3 1 2 1 0 1 3 2 0 2 3 4 1 |
1 |
| 3 |
3 1 2 1 0 1 3 2 1 2 3 4 1 |
0 |
典型的最小生成树问题，刚开始用了普鲁姆算法，结果提示超时和段错误。超时好理解，段错误真的不知道为什么。
贴一下代码：
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[101][102]={0};
int visit[102]={0};
int p[102]={0};
int n=0;
#define inf 0x3f3f3f3f
int prime()
{
int min=0;
int sum=0;
int cnt=0;
int j=0,i=0,k=0;
for(i=0;i<n;i++)
{
min=inf;
for(j=2;j<=n;j++)//在候选边里面找一条最小的
{
if((visit[j]!=1)&&p[j]<min)
{
min=p[j];
cnt=j;
}
}
if(min!=inf)
{
sum+=min;
visit[cnt]=1;//已经访问过了
for(k=2;k<=n;k++)//更新权值
{
if((visit[k]!=1)&&(p[k]>a[cnt][k]))
{
p[k]=a[cnt][k];
}
}
}
}
return sum;
}
int main()
{
int N=0;
int i=0,j=0,flag=0,d=0;
memset(a,inf,sizeof(a));
scanf("%d",&N);
N=N*(N-1)/2;
n=N;
while(N--){
scanf("%d%d%d%d",&i,&j,&d,&flag);
a[i][j]=d;
if(flag==0)
{
a[j][i]=a[i][j];
}else
{
a[j][i]=0;
a[i][j]=0;
}
}
for(i=1;i<=n;i++)
{
p[i]=a[1][i];
}
visit[1]=1;//取1号点为生成树
int ans=0;
ans=prime();//普鲁姆算法 取点
printf("%d\n",ans);
return 0;
}
后来在网上找到了答案，发现他的代码也是普鲁姆算法，只不过有一些不一样。为了缩短时间和内存，他做了一点改进省略了这一段：
for(i=1;i<=n;i++)
{
p[i]=a[1][i];
}
直接利用那个a[][]这个数组，感觉也没差多少，因为这段的时间复杂度也就O（n）和本身整体的复杂度O(n^2)相比应该是可以忽略的。后来又仔细看了一下题目时间限制：10MS，比一般的题目都要少很多，一般题目有400MS。所以这也可能是一个因素把。至于段错误真不知道错哪里了，有知道的希望可以告知，不胜感激。
附网上的答案：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
int map[100][100];
int s[100],vis[100];
int n,m;
int prim()
{
int i,j,t,p,min,cnt,minpos;
int ans=0;
cnt=0;
vis[1]=1;
s[cnt++]=1;
while(cnt<n)
{
t=cnt;
min=inf;
for(i=0;i<t;i++)
{
p=s[i];
for(j=1;j<=n;j++)
{
if(!vis[j]&&map[p][j]<min)
{
min=map[p][j];
minpos=j;
}
}
}
ans+=min;
s[cnt++]=minpos;
vis[minpos]=1;
}
return ans;
}
int main()
{
int i,sum;
while(~scanf("%d",&n)&&n)
{
memset(vis,0,sizeof(vis));
memset(map,inf,sizeof(map));
int b,c,d,sta;
m=n*(n-1)/2;
for(i=0;i<m;i++)
{
scanf("%d%d%d%d",&b,&c,&d,&sta);
if(sta==0)
map[b][c]=map[c][b]=d;
else
map[b][c]=map[c][b]=0;
}
sum=prim();
printf("%d\n",sum);
}
return 0;
}