沟里国家生死一

#include "iostream"
#include "map"
#include "cstring"
#include "algorithm"
#define MAXN 10010
#define init(a,b) memset(a,b,sizeof(a))

using namespace std;

int cnt=1;
int rep[MAXN];
int n;

struct Edge
{
int from;
int to;
int value;
bool operator < (const Edge &a)
{
return this->value<a.value;
}
}e[MAXN];

bool comp(const Edge &a,const Edge &b)
{
return a.value<b.value;
}

void Initialize()
{
cnt=1;
init(rep,0);
init(e,0);
}

int Find(int x)
{
if(x!=rep[x]) rep[x]=Find(rep[x]);
return rep[x];
}

void Union(int a,int b)
{
rep[Find(a)]=Find(b);
}

int Kruskal()
{
int ans=0;
sort(e,e+cnt);
for(int i=1;i<=cnt;i++)
{
int a=e[i].from,b=e[i].to;
if(Find(a)!=Find(b))
{
Union(a,b);
ans+=e[i].value;
}
}
return ans;
}

void Add_Edge(int x,int y,int p)
{
e[++cnt].to=y;
e[cnt].from=x;
e[cnt].value=p;
}

int main()
{
cin>>n;
while(n)
{
Initialize();
for(int k=1;k<=n-1;k++)
{
char u;
cin>>u;
int edge;
cin>>edge;
for(int i=1;i<=edge;i++)
{
char v;
int p;
cin>>v>>p;
int x=u-'B',y=v-'B';
Add_Edge(x,y,p);
}
}
cout<<Kruskal()<<endl;
cin>>n;
}
return 0;
}

3 条评论

  • 1

信息

ID
1000
难度
9
分类
(无)
标签
(无)
递交数
60430
已通过
24192
通过率
40%