POJ 1679회 작은 스패닝 트리

제목 대의, t조 예시 입력, n개 점 m변, 최소 생성 트리 이외의 최단 변을 구합니다.
폭력, 폭력, 데이터 워터, 폭력은 기적을 일으킨다
시뮬레이션 각 최소 생성 트리의 모서리를 선택하지 않고 최소
코드
By Acer.Mo
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct edge
{
	int to;
	int from;
	int cost;
	bool friend operator < (edge a,edge b)
	{
		return a.cost>b.cost;	
	}	
}g[10000];
int sortt[10000],soid=0;
int n,m;
int father[10000];
int find(int x)
{
	if (x!=father[x]) father[x]=find(father[x]);
	return father[x];
}
void unionn(int a,int b)
{
	father[b]=a;
	return ;
} 
void constt()
{
	for (int i=1;i<=n;i++)
	{
		father[i]=i;
	}
}
int Kul()
{
	int ans=0,tot=1;
	for (int i=1;i<=m;i++)
	{
		int r1=find(g[i].from);
		int r2=find(g[i].to);
		if (r1!=r2)
		{
			tot++;
			unionn(r1,r2);
			ans+=g[i].cost;
			sortt[soid++]=i;
			if (tot==n) break;
		}
	}
	if (tot

좋은 웹페이지 즐겨찾기