POJ 1679 解题报告

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

这道题是判断最小生成树是否唯一。

方法之一（也是显而易见正确的方法）是求次小生成树，然后看两者的值是否一样。一样则不唯一。ByVoid有对次小生成树（及次短路径）的讲解（https://www.byvoid.com/blog/2-sp-mst）。还有对这道题的讲解（https://www.byvoid.com/blog/pku-1679/）。

方法之二是感觉正确性比较难判断的方法。即用kruskal求最小生成树，在这过程中，对每条加入最小生成树的边，判断是否有另外一条“替代边”也可以加入。“替代边”即weight相等，同时两个节点的父节点一样。这样这条“替代边”加入对最小生成树没影响（而且这两条边只可能加入一条，因为加入后就将两个tree连接起来了）。我刚开始思路有些混乱，看了discuss这里（http://poj.org/showmessage?message_id=346724）才清晰一些。

thestoryofsnow

1679

Accepted

188K

16MS

C++

2688B

画图程序：

import networkx as nx
import matplotlib.pyplot as pltG = nx.Graph()
with open("input1.txt") as f:f.readline()n, m = map(int, f.readline().strip().split())G.add_nodes_from(range(1, n + 1))# print n, mfor _ in range(m):u, v, w = [int(x) for x in f.next().strip().split()]# print "line:[" + str(line) + "](" + str(len(line)) + ")"# u, v, w = line[0], line[1], line[2]print "u:", u, ", v:", v, ", w:", wG.add_edge(u, v, weight = w, length = w)pos = nx.graphviz_layout(G)
# pos = nx.spring_layout(G)
nx.draw(G, pos)edge_labels = dict([((u, v), d['weight'])for u, v, d in G.edges(data = True)])
print 'edge_labels:', edge_labels
nx.draw_networkx_edge_labels(G, pos, edge_labels = edge_labels)labels = {u : str(u) for u in G.nodes()}
nx.draw_networkx_labels(G, pos, labels, font_size = 10)# nx.draw_networkx(G)
# plt.show()
plt.savefig("networkx.png")print G.nodes()
print G.edges()

c++程序：

/* 
ID: thestor1 
LANG: C++ 
TASK: poj1679 
*/
#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;const int MAXN = 100, MAXM = MAXN * (MAXN - 1) / 2;void makeset(const int N, int parent[], int rank[])
{for (int u = 0; u < N; ++u){parent[u] = u;rank[u] = 0;}
}int find(int u, int parent[])
{if (parent[u] != u){parent[u] = find(parent[u], parent);}return parent[u];
}void union_set(int u, int v, int parent[], 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(Edge edges[], int parent[], int rank[], const int n, const int m, bool &isUnique)
{makeset(n, parent, rank);sort(edges, edges + m);int mst = 0;for (int i = 0; i < m; ++i){int pui = find(parent[edges[i].u], parent), pvi = find(parent[edges[i].v], parent);if (pui == pvi){continue;}for (int j = i + 1; j < m && edges[j].w == edges[i].w; j++){int puj = find(parent[edges[j].u], parent), pvj = find(parent[edges[j].v], parent);if ((pui == puj && pvi == pvj) || (pui == pvj && pvi == puj)){// printf("(%d, %d)[%d] is NOT unique with (%d, %d)[%d]\n", edges[i].u + 1, edges[i].v + 1, edges[i].w, edges[j].u + 1, edges[j].v + 1, edges[j].w);isUnique = false;return -1;}}// printf("adding (%d, %d)[%d] to mst\n", edges[i].u + 1, edges[i].v + 1, edges[i].w);mst += edges[i].w;union_set(edges[i].u, edges[i].v, parent, rank);}return mst;
}int main()
{int T;scanf("%d", &T);int parent[MAXN], rank[MAXN];Edge edges[MAXM];for (int t = 0; t < T; ++t){int n, m;scanf("%d%d", &n, &m);for (int i = 0; i < m; ++i){int u, v, w;scanf("%d%d%d", &u, &v, &w);u--, v--;edges[i].u = u, edges[i].v = v, edges[i].w = w;}if (m < n - 1){printf("0\n");continue;}bool isUnique = true;int mst = kruskal(edges, parent, rank, n, m, isUnique);if (isUnique){printf("%d\n", mst);}else{printf("Not Unique!\n");}}return 0;  
}

 

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

---