POJ 1258 解题报告

本文主要是介绍POJ 1258 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题是实现最小生成树。我用的时kruskal的方法，用到了union-find算法（union似乎是c++的一个关键字）。值得注意的地方是数据有多组输入，所以需要写while。我因此贡献了一次WA。

kruskal: http://en.wikipedia.org/wiki/Kruskal%27s_algorithm

union-find: http://en.wikipedia.org/wiki/Disjoint-set_data_structure

kruskal非常快。如果edges, parent, rank变成全局变量，静态分配，重复利用的话估计用时会更少。

1258

Accepted

384K

47MS

C++

2113B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj1258 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;void makeset(const int N, std::vector<int> &parent, std::vector<int> &rank)
{for (int u = 0; u < N; ++u){parent[u] = u;rank[u] = 0;}
}int find(int u, std::vector<int> &parent)
{if (parent[u] != u){parent[u] = find(parent[u], parent);}return parent[u];
}void union_set(int u, int v, std::vector<int> &parent, std::vector<int> &rank)
{int ru = find(u, parent);int rv = find(v, parent);if (ru == rv){return;}if (rank[ru] < rank[rv]){parent[ru] = rv;}else if (rank[rv] < rank[ru]){parent[rv] = ru;}else{parent[ru] = rv;rank[rv]++;}
}class Edge
{
public:int u, v, w;Edge() {}Edge(int u, int v, int w) : u(u), v(v), w(w) {}bool operator< (const Edge &rhs) const{if (this->w != rhs.w){return this->w < rhs.w;}return this->u < rhs.u || (this->u == rhs.u && this->v < rhs.v);}
};int kruskal(const int N, std::vector<Edge> &edges)
{std::vector<int> parent(N);std::vector<int> rank(N);makeset(N, parent, rank);sort(edges.begin(), edges.end());int mst = 0;for (int i = 0; i < edges.size(); ++i){Edge edge = edges[i];if (find(edge.u, parent) != find(edge.v, parent)){mst += edge.w;union_set(edge.u, edge.v, parent, rank);}}return mst;
}int main()
{int N;while (cin >> N){// std::vector<std::vector<int> > dis(N, std::vector<int>(N, 0));std::vector<Edge> edges;int w;for (int u = 0; u < N; ++u){for (int v = 0; v < N; ++v){cin >> w;if (u < v){edges.push_back(Edge(u, v, w));}}}int mst = kruskal(N, edges);cout << mst << endl;}return 0;  
}

这篇关于POJ 1258 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---