POJ 1278 Agri - Net 최소 생 성 트 리 템 플 릿 문제 (Prim 과 Kruskal)

이것 은 저의 첫 번 째 oj 기록 박문 입 니 다. 앞으로 많은 지도 바 랍 니 다.오늘 은 poj 3241 맨 해 튼 에서 가장 작은 생 성 트 리 문 제 를 풀 려 고 했 는데 반나절 을 배 웠 더 니 Kruskal 도 제대로 이 루어 지지 않 는 다 는 것 을 알 고 돌아 와 서 최소 템 플 릿 문제 의 이 문 제 를 다시 풀 었 고 이전의 prim 알고리즘 의 해법 코드 와 함께 보 냈 다.
Prim 과 Kruskal 알고리즘 은 모두 최소 생 성 트 리 를 푸 는 효과 적 인 방법 이지 만 이들 의 효율 적 인 실현 은 모두 교묘 한 데이터 구조 에 의존한다.Kruskal 알고리즘 을 사용 하여 집합 을 찾 으 면 O (E * alpha (E)) 의 풀이 시간 (그 중에서 alpha 함 수 는 증가 와 느 린 함수 이 고 여기 서 상수 로 볼 수 있 습 니 다) 에 도달 할 수 있 습 니 다. 또한 정렬 시간 을 더 하면 총 시간 은 O (E log (E) 입 니 다. prim 알고리즘 에 서 는 최소 우선 대기 열 을 유지 하고 O (1) 를 요구 합 니 다.시간 내 에 요 소 를 찾 고 값 을 바 꾸 었 습 니 다. 저 는 좋 은 방법 을 알 지 못 했 습 니 다. 이 진 더미 의 요 소 를 찾 는 시간 은 O (n) 이기 때문에 배열 로 유지 하 는 것 이 좋 습 니 다.
poj 1278 문제 면 은 여기 서 더 이상 군말 하지 않 습 니 다. 바로 정점 < 100 의 최소 생 성 트 리 의 문제 입 니 다. 다음은 개인 코드 를 첨부 합 니 다. 프로 그래 밍 습관 은 camelVariant 명명 법 을 사용 합 니 다. 또한 변수 이름 이 비교적 길 기 때문에 많이 양해 해 주 십시오.
Prim 방법:

#include 
#include 
#define Size 101

typedef int iter;
int farms[Size][Size];
struct Vertex {
	int key;
	int piNumber;
	bool isValid;
};
typedef struct Vertex Vertex;
Vertex vertices[Size];
int extractMin(int size) 
{
	int isNull = true;
	int tempMin = INT_MAX;
	int tempMinIndex = -1;
	for (int i = 0; i < size; i++) {
		if (!vertices[i].isValid)
			continue;
		else {
//			printf("Here.
");
			isNull = false;
			if (tempMin > vertices[i].key) {
				tempMinIndex = i;
				tempMin = vertices[i].key;
			}
		}
	}
//	printf("TempMinIndex:%d
", tempMinIndex);
	if (!isNull) {
		vertices[tempMinIndex].isValid=false;
	}
	return tempMinIndex;
}
bool isBeLong(int size,int checkNumber)
{
	return vertices[checkNumber].isValid && size > checkNumber;
}
int main()
{
	iter i, j, k;
	int size,temp;
	while (scanf("%d", &size) != EOF) {
		for (i = 0; i < size; i++)
			for (j = 0; j < size; j++)
				scanf("%d", &farms[i][j]);
/*		for (i = 0; i < size; i++) {
			for (j = 0; j < size; j++) {
				printf("%d", farms[i][j]);
				j == size - 1 ? printf("
") : printf("\t");
			}
		}*/
		
		for (i = 0; i < size; i++) {
			vertices[i].piNumber = -1;
			vertices[i].key =1000000;
			vertices[i].isValid = true;
		}
		temp = extractMin(size);
		while (temp >= 0) {
//			printf("Temp:%d
", temp);
			for (i = 0; i < size; i++) {
				if (i != temp) {
					if (farms[temp][i] < vertices[i].key&&isBeLong(size, i)) {
						vertices[i].piNumber = temp;
						vertices[i].key = farms[temp][i];
					}
				}
			}
			temp = extractMin(size);
		}
		int value = 0;
		for (int i = 0; i < size; i++)
			value += farms[i][vertices[i].piNumber];
		printf("%d
", value);
	}
	return 0;
}

Kruskal 방법:

#include 
#include 
#include 
#include 
#include 
using namespace std;

struct Edge {
	int from;
	int to;
	int weight;
	bool operator < (const Edge& ele) {
		return this->weight < ele.weight;
	}
};
typedef struct Edge Edge;

class KruskalGraph
{
public:
	void init(int n)
	{
		this->edges.clear();
		this->vertices.clear();
		for (int i = 0; i < n; i++)
			this->vertices.push_back(-1);
		this->treeEdges.clear();
		this->order = n;
	}
	void Inserto(int u, int v, int w)
	{
		Edge tempEdge;
		tempEdge.from = u;
		tempEdge.to = v;
		tempEdge.weight = w;
		this->edges.push_back(tempEdge);
	}
	void Kruskal()
	{
		sort(edges.begin(), edges.end());
		int count = 0;
		for (int i = 0; i < edges.size()&&counttreeEdges.push_back(edges[i]);
				Union(root1, root2);
				count++;
			}
		}
	}
	void showMST()
	{
		for (int i = 0; i < treeEdges.size(); i++) {
			printf("(%d,%d,%d) ", treeEdges[i].from, treeEdges[i].to, treeEdges[i].weight);
		}
		printf("
");
	}
	int mstValu()
	{
		int ret = 0;
		for (int i = 0; i < treeEdges.size(); i++)
			ret += treeEdges[i].weight;
		return ret;
	}
private:
	vector edges;
	vector treeEdges;
	vector vertices;
	int order;
	void Union(int x, int y)
	{
		int root1, root2;
		root1 = Find(x);
		root2 = Find(y);
		//printf("Roots:%d %d
", root1, root2);
		_union(root1, root2);
	}
	int Find(int x)
	{
		if (vertices[x] < 0)
			return x;
		else
			return vertices[x] = Find(vertices[x]);
	}
	void _union(int x, int y)
	{
		if (vertices[y] < vertices[x]) {
			vertices[x] = y;
		}
		else {
			if (vertices[x] == vertices[y])
				vertices[x]--;
			vertices[y] = x;
		}
	}
};
int main()
{
	int n;
	KruskalGraph graph;
	while (scanf("%d", &n) != EOF) {
		graph.init(n);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int weight;
				scanf("%d", &weight);
				if (i > j)
					graph.Inserto(i, j, weight);
			}
		}
		graph.Kruskal();
		//graph.showMST();
		printf("%d
", graph.mstValu());
	}
	return 0;
}

그리고 오늘 배 운 두 개의 템 플 릿 을 동봉 합 니 다.
하나의 집합:

class UnionFindSet : vector
{
public:
	UnionFindSet(int k)
	{
		this->clear();
		for (int i = 0; i < k; i++) {
			this->push_back(-1);
		}
	}
	void show()
	{
		for (int i = 0; i < this->size(); i++) {
			printf("%d ", (*this)[i]);
		}
		printf("
");
	}
	int find(int x)
	{
		if ((*this)[x] < 0)
			return x;
		else
			return (*this)[x] = find((*this)[x]);
	}
	void Union(int x, int y)
	{
		int root1, root2;
		root1 = find(x);
		root2 = find(y);
		printf("Roots:%d %d
", root1, root2);
		_union(root1, root2);
	}
private:
	void _union(int x, int y)
	{
		if ((*this)[y] < (*this)[x]) {
			(*this)[x] = y;
		}
		else {
			if ((*this)[x] == (*this)[y])
				(*this)[x]--;
			(*this)[y] = x;
		}
	}
};

또 다른 사람의 Binary Indexed Tree 는 내일 맨 해 튼 트 리 를 풀 때 쓸 수 있 는 문 제 를 먼저 배 워 보 세 요.

class BinTree : vector
{
public:
	explicit BinTree(int k = 0) {
		assign(k + 1, 0);
	}
	int sum(int k)
	{
		return k > 0 ? sum(k - lowBit(k)) + (*this)[k] : 0;
	}
	int last()
	{
		return size() - 1;
	}
	void add(int k, int w)
	{//for adding w to node k
		if (k > last())
			return;
		(*this)[k] += w;
		add(k + lowBit(k), w);
	}
	void show(int start, int end)
	{
		for (int i = start; i <= end; i++) {
			printf("%d ", (*this)[i]);
		}
		printf("
");
	}
	void show()
	{
		for (int i = 0; i < this->size(); i++) {
			printf("%d ", (*this)[i]);
		}
		printf("
");
	}
private:
	int lowBit(int k)
	{
		return k&-k;
	}
};

오늘 은 여기까지 쓰 겠 습 니 다. 상술 한 기술적 인 세부 사항 은 제 가 나중에 글 을 쓰 는 과정 에서 시간 이 있 을 때 언급 하 겠 습 니 다. 앞으로 도 잘 부탁드립니다.