先上题

Description

The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They’re planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.

Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways.

The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town.

Input

The first line of input is an integer T, which tells how many test cases followed.

The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case.

Output

For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

Sample Input

1

3

0 990 692

990 0 179

692 179 0

Sample Output

692

这是一道简单的最小生成树的直接应用题，先用prim算法。

我先简单阐述一下prim算法的核心思想。

对于n个节点的网或者说图，只需要n-1条边即可将所有节点连通，由所有节点生成的一棵树。而对于这n个节点，最多有n(n-1)/2条边，那么选择哪些边可以使这棵树的权值最小呢。两个最小生成树算法用运用了一个叫MST的原理。

MST原理

那么MST原理是什么呢？

在图<V,E>中,V为顶点的集合，E为所有边的集合。将顶点分为两个集合，V1和V2，并且假设边（u，v）是连通顶点集V1和V2的最小的边，并且，u属于V1,v属于V2。那么最终生成的最小生成树中，一定包含有（u，v）这条边。因为是生成树，顶点集1和顶点集V2之间必定是一条边来连通彼此。如果这条边不是（u，v）这条边，则是另外一条边e1，而（u，v）这边的权值比e1的权值更小，如果换成（u，v）这边，则生成树的权值会更小，所有e1的这条边的生成树不是最小生成树。即最小生成树必定含有（u，v）这条边。

prim算法

第一步

顶点集V1包含所有的顶点，从所有的顶点集中任选一个顶点放入已选顶点集V1中，并将该顶点从V1中删除

第二步

选择一条连通顶点集V1和V2的权值最小的边，并将该顶点从V1中删除，加入V2。

第三步

重复第二步，直到顶点集V1中的顶点为空

运用prim算法解该题

顶点集直接用C++中的集合来表示，插入和删除均非常方便，插入和删除的时间复杂度是O(logn)

#include<iostream>
#include<vector>
#include<set>
#include<iterator>

using namespace std;

int main(void){
	
	int t;
	int n;
	for(cin>>t;t;t--){
		cin>>n;
		vector<vector<int>> dist(n);
		int dis;
		for(int i = 0;i<n;i++)
			for(int j = 0;j<n;j++){
				cin>>dis;
				dist[i].push_back(dis);
			}
		set<int> visited;
		set<int> unvisited;
		visited.insert(0);
		for(int i = 1;i<n;i++)
			unvisited.insert(i);
		set<int>::iterator p,q;
		int maxdis = -1;
		while(unvisited.size()){
			int mindis = 999999;
			int obj;
			for(p=visited.begin();p!=visited.end();p++){
				for(q = unvisited.begin();q!=unvisited.end();q++){
					if(dist[*p][*q]<mindis){
						mindis = dist[*p][*q];
						obj = *q;
					}
				}
			}
			if(mindis>maxdis)
				maxdis = mindis;
			visited.insert(obj);
			unvisited.erase(obj);
		}
		
		cout<<maxdis<<endl;
		
	} 
	
	
	return 0;
}

一次过AC了，但是这个算法的时间复杂度是O(n^3)，可以AC，但是运行时间比较大。