UC知道poj1251 帮看下kruscal为什么超时
来源：百度知道 编辑：UC知道 时间：2024/05/18 17:57:19
prim一遍就过了 kruscal测试数据顺利过了,不过提交就是Runtime Error,也没可以溢出的地方啊
#include <iostream>
#include <algorithm>
using namespace std;
int k;
int n;
int ans;
int f[900];
int gef(int);
void unite(int,int);
void kruscal();
struct edge
{
int a,b;
int w;
}e[900];
int main()
{
while(cin>>n&&n!=0)
{
k=0;
int i,j;
char c,c1;
int d,d1;
for(i=0;i<n-1;i++)
{
cin>>c>>d;
for(j=0;j<d;j++)
{
cin>>c1>>d1;
e[k].a=c-'A';
e[k].b=c1-'A';
e[k].w=d1;
k++;
}
}
kruscal();
cout<<ans<<endl;
}
return 0;
}
int getf(int a)
{
if(f[a]!=a) f[a]=getf(f[a]);
return f[a];
}
void unite(int a,int b)
{
int i,j;
i=getf(a);
j
#include <iostream>
#include <algorithm>
using namespace std;
int k;
int n;
int ans;
int f[900];
int gef(int);
void unite(int,int);
void kruscal();
struct edge
{
int a,b;
int w;
}e[900];
int main()
{
while(cin>>n&&n!=0)
{
k=0;
int i,j;
char c,c1;
int d,d1;
for(i=0;i<n-1;i++)
{
cin>>c>>d;
for(j=0;j<d;j++)
{
cin>>c1>>d1;
e[k].a=c-'A';
e[k].b=c1-'A';
e[k].w=d1;
k++;
}
}
kruscal();
cout<<ans<<endl;
}
return 0;
}
int getf(int a)
{
if(f[a]!=a) f[a]=getf(f[a]);
return f[a];
}
void unite(int a,int b)
{
int i,j;
i=getf(a);
j
贴个kruskal：
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,f[105],k;
struct sth
{
int x,y,w;
}s[105];
bool cmp(sth x,sth y)
{
return x.w<y.w;
}
int find(int x)
{
if(x!=f[x]) return f[x]=find(f[x]);
else return f[x];
}
void kruskal()
{
int ans=0;
for(int i=1;i<=n;i++)f[i]=i;
sort(s+1,s+m+1,cmp);
for(int i=1;i<=m;i++)
{
int p=find(s[i].x);
int q=find(s[i].y);
if(q!=p)
{
ans+=s[i].w;
f[q]=p;
}
}
bool flag=true;
for(int i=1;i<n;i++)
{
if(find(i)!=find(i+1))
{
flag=false;
break;
}
}
if(flag)printf("%d\n",ans);
else printf("?\n");
}
int main()