關於最小生成樹的編程題：天氣晴朗的魔法

02-03

51Nod上有這樣一道編程題：

題目號是1640。

經@Shawn Wu和@懸客提示，解題思路是：先求出最小生成樹中邊的最大權值W，然後再在限定邊權值不得超過W的情況下求解最大生成樹。

答案是

#include <cstdio>n#include <vector>n#include <list>n#include <functional>n#include <utility>n#include <algorithm>nnusing namespace std;nn#define Parent(i) ( ((i) - 1 ) >> 1 )n#define Left(i) ( ((i) << 1) | 1 )n#define Right(i) ( ((i) + 1 ) << 1 )nnstruct VertexKeyn{ntint m_VertexIndex;ntint m_Key;ntVertexKey(int index, int k) : m_VertexIndex(index), m_Key(k){}n};nnstruct VertexKeyLessn{ntbool operator()(const VertexKey &l, const VertexKey &r) constnt{nttif (l.m_Key == r.m_Key)ntttreturn l.m_VertexIndex < r.m_VertexIndex;nttreturn l.m_Key < r.m_Key;nt}n};nnstruct VertexKeyGreatern{ntbool operator()(const VertexKey &l, const VertexKey &r) constnt{nttif (l.m_Key == r.m_Key)ntttreturn l.m_VertexIndex > r.m_VertexIndex;nttreturn l.m_Key > r.m_Key;nt}n};nntemplate <class KeyCompare = VertexKeyLess, class IntCompare = less<int> >nstruct PrimHeapn{ntvector<VertexKey> m_HeapData;ntvector<int> m_IndexInHeap;ntPrimHeap(const vector<VertexKey> &keys);ntvoid HeapElementSwap(int i, int j);ntvoid Heapify(int i);ntbool IsEmpty() const;ntVertexKey GetTop() const;ntVertexKey ExtractTop();ntint ModifyKey(int i, int key);n};nntemplate <class KeyCompare, class IntCompare>nPrimHeap<KeyCompare, IntCompare>::PrimHeap(const vector<VertexKey> &keys)n: m_HeapData(keys), m_IndexInHeap(keys.size())n{ntfor (int i = 0; i < m_IndexInHeap.size(); ++i)nttm_IndexInHeap[i] = m_HeapData[i].m_VertexIndex;ntfor (int i = m_HeapData.size() / 2 - 1; i >= 0; --i)nttHeapify(i);n}nntemplate <class KeyCompare, class IntCompare>nvoid PrimHeap<KeyCompare, IntCompare>::HeapElementSwap(int i, int j)n{ntint i_vertex_index = m_HeapData[i].m_VertexIndex;ntint j_vertex_index = m_HeapData[j].m_VertexIndex;ntm_IndexInHeap[i_vertex_index] = j;ntm_IndexInHeap[j_vertex_index] = i;ntswap(m_HeapData[i], m_HeapData[j]);n}nntemplate <class KeyCompare, class IntCompare>nvoid PrimHeap<KeyCompare, IntCompare>::Heapify(int i)n{ntif (i < 0 || i >= m_HeapData.size())nttreturn;ntint target = i, L = Left(i), R = Right(i);ntif (L >= 0 && L < m_HeapData.size() && KeyCompare()(m_HeapData[L], m_HeapData[i]))ntttarget = L;ntif (R >= 0 && R < m_HeapData.size() && KeyCompare()(m_HeapData[R], m_HeapData[target]))ntttarget = R;ntif (target == i)nttreturn;ntHeapElementSwap(i, target);ntHeapify(target);n}nntemplate <class KeyCompare, class IntCompare>nbool PrimHeap<KeyCompare, IntCompare>::IsEmpty() constn{ntreturn m_HeapData.empty();n}nntemplate <class KeyCompare, class IntCompare>nVertexKey PrimHeap<KeyCompare, IntCompare>::GetTop() constn{ntreturn m_HeapData[0];n}nntemplate <class KeyCompare, class IntCompare>nVertexKey PrimHeap<KeyCompare, IntCompare>::ExtractTop()n{ntVertexKey rt = m_HeapData[0];ntHeapElementSwap(0, m_HeapData.size() - 1);ntm_IndexInHeap[m_HeapData.back().m_VertexIndex] = -1;ntm_HeapData.pop_back();ntHeapify(0);ntreturn rt;n}nntemplate <class KeyCompare, class IntCompare>nint PrimHeap<KeyCompare, IntCompare>::ModifyKey(int i, int key)n{ntif (!IntCompare()(key, m_HeapData[i].m_Key))nttreturn -1;ntm_HeapData[i].m_Key = key;ntwhile (i > 0 && !IntCompare()(m_HeapData[Parent(i)].m_Key, m_HeapData[i].m_Key))nt{nttHeapElementSwap(i, Parent(i));ntti = Parent(i);nt}ntreturn 0;n}nntypedef PrimHeap<VertexKeyLess, less<int> > PrimMinHeap;ntypedef PrimHeap<VertexKeyGreater, greater<int> > PrimMaxHeap;nnstruct Edgen{ntint m_start;ntint m_end;ntint m_weight;ntEdge(int start = -1, int end = -1, int weight = INT_MAX)ntt: m_start(start), m_end(end), m_weight(weight){}n};nnstruct Vertexn{ntlist<Edge> m_edges;n};nnstruct Graphn{ntvector<Vertex> m_vertexes;ntGraph(int N) : m_vertexes(N){}ntlong long int MinPrim(int r);ntlong long int MaxPrim(int r, long long int ref);n};nnlong long int Graph::MinPrim(int r)n{ntvector<Edge> resultedges;ntvector<int> parent(m_vertexes.size(), -1);ntvector<VertexKey> keys(m_vertexes.size(), VertexKey(0, INT_MAX));ntfor (int i = 0; i < m_vertexes.size(); ++i)nttkeys[i].m_VertexIndex = i;ntkeys[r].m_Key = 0;ntPrimMinHeap Q(keys);ntint ret = INT_MIN;ntwhile (!Q.IsEmpty())nt{nttVertexKey t = Q.ExtractTop();nttint u = t.m_VertexIndex, w = t.m_Key;nttif (parent[u] != -1)ntt{ntttresultedges.push_back(Edge(parent[u], u, w));ntttret = max(ret, w);ntt}nttfor (auto itr = m_vertexes[u].m_edges.begin(); itr != m_vertexes[u].m_edges.end(); ++itr)ntt{ntttint v = itr->m_end;ntttif (Q.m_IndexInHeap[v] != -1 && itr->m_weight < Q.m_HeapData[Q.m_IndexInHeap[v]].m_Key)nttt{nttttparent[v] = u;nttttQ.ModifyKey(Q.m_IndexInHeap[v], itr->m_weight);nttt}ntt}nt}ntreturn ret;n}nnlong long int Graph::MaxPrim(int r, long long int ref)n{ntvector<Edge> result;ntvector<int> parent(m_vertexes.size(), -1);ntvector<VertexKey> keys(m_vertexes.size(), VertexKey(0, INT_MIN));ntfor (int i = 0; i < m_vertexes.size(); ++i)nttkeys[i].m_VertexIndex = i;ntkeys[r].m_Key = 0;ntPrimMaxHeap Q(keys);ntwhile (!Q.IsEmpty())nt{nttVertexKey t = Q.ExtractTop();nttint u = t.m_VertexIndex, w = t.m_Key;nttif (parent[u] != -1)ntttresult.push_back(Edge(parent[u], u, w));nttfor (auto itr = m_vertexes[u].m_edges.begin(); itr != m_vertexes[u].m_edges.end(); ++itr)ntt{ntttint v = itr->m_end;ntttif (Q.m_IndexInHeap[v] != -1 && itr->m_weight <= ref && itr->m_weight > Q.m_HeapData[Q.m_IndexInHeap[v]].m_Key)nttt{nttttparent[v] = u;nttttQ.ModifyKey(Q.m_IndexInHeap[v], itr->m_weight);nttt}ntt}nt}ntlong long int W = 0LL;ntfor (auto itr = result.begin(); itr != result.end(); ++itr)nttW += itr->m_weight;ntreturn W;n}nnint main()n{ntint N = 0, M = 0;ntscanf("%d%d", &N, &M);ntGraph g(N);ntfor (int i = 0; i < M; ++i)nt{nttint s = 0, e = 0, w = 0;nttscanf("%d%d%d", &s, &e, &w);nttg.m_vertexes[s - 1].m_edges.push_back(Edge(s - 1, e - 1, w));nttg.m_vertexes[e - 1].m_edges.push_back(Edge(e - 1, s - 1, w));nt}ntlong long int rt = g.MinPrim(0);ntlong long int W = g.MaxPrim(0, rt);ntprintf("%lldn", W);ntreturn 0;n}n