Tan cong thanh tri krukal

 avatar
unknown
plain_text
a year ago
1.6 kB
8
Indexable
// Tan cong thanh tri krukal
#include<iostream>
using namespace std;

#define N 100

int T, soThanhTri, soHieu, soMay, soLienKet, adj[N][N];
int st[N*N], en[N*N], dist[N*N], parent[N*N], edge; 

void makeSet(int x)
{
	parent[x]=x;
}

int findSet(int x)
{
	if(x==parent[x]) return x;
	return findSet(parent[x]);
}

void join(int x, int y)
{
	parent[findSet(y)]=findSet(x);
}

void swap(int i, int j)
{
	int tmp=st[i]; st[i]=st[j]; st[j]=tmp;
	 tmp=en[i]; en[i]=en[j]; en[j]=tmp;
	 tmp=dist[i]; dist[i]=dist[j]; dist[j]=tmp;
}

void sort()
{
	for(int i=0;i<edge-1;i++)
		for(int j=i+1;j<edge;j++)
			if(dist[i]<dist[j])
				swap(i,j);
}

int main()
{
	freopen("a.txt","r",stdin);
	cin>>T;
	int v;
	for(int tc=1;tc<=T;tc++)
	{
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				adj[i][j]=0;

		edge=0;
		cin>>soThanhTri;
		for(int t=0;t<soThanhTri;t++)
		{
			cin>>soHieu>>soMay>>soLienKet;
			makeSet(soHieu);
			for(int i=0;i<soLienKet;i++)
			{
				cin>>v;
				adj[soHieu][v] += soMay;
				adj[v][soHieu] = adj[soHieu][v];
			}
		}

		for(int i=0;i<soThanhTri;i++)
		{
			for(int j=i+1;j<soThanhTri;j++)
			{
				if(adj[i][j])
				{
					dist[edge]=adj[i][j];
					st[edge]=i;
					en[edge++]=j;
				}
			}
		}

		sort();
		int ans=0;
		for(int i=0;i<edge;i++)
		{
			int u=findSet(st[i]);
			int v=findSet(en[i]);
			if(u==v)
				ans+=dist[i];
			else
			{
				join(u,v);
			}
		}

		for(int i=0;i<edge;i++)
		{
			dist[i]=0;
			parent[i]=0;
			st[i]=0;
			en[i]=0;
		}

		cout<<ans<<endl;
	}

	return 0;
}
Editor is loading...
Leave a Comment