题目训练网址（密码hpuacm）： https://cn.vjudge.net/contest/247189 

//#include <bits/stdc++.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAXN = 500+7;
const int INF = 0x3f3f3f3f;

int cost[MAXN][MAXN];
int mincost[MAXN];
bool vis[MAXN];
int n;
void prim()
{
	memset(vis, 0, sizeof(vis));
	for( int i=1; i<=n; i++ )
		mincost[i] = cost[1][i];
	int ans = -1;
	//int u, v;
	while( true )
	{
		int v = -1;
		for( int u=1; u<=n; u++ )
			if( !vis[u] && (v == -1 || mincost[u] < mincost[v]) )
				v = u;
		if( v == -1 ) break;
		vis[v] = 1;
		ans = max(ans, mincost[v]);
		for( int u=1; u<=n; u++ )
			mincost[u] = min(mincost[u], cost[v][u]);
	}
	printf("%d\n", ans);
}

int main()
{
	int t;
	scanf("%d", &t);
	while( t-- )
	{
		scanf("%d", &n);
		for( int i=1; i<=n; i++ )
			for( int j=1; j<=n; j++ )
				scanf("%d", &cost[i][j]);
		prim();
	}

    return 0;
}
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
const int MAXN = 100 + 7;

struct node{
    int a, b, c;
};
struct node road[(MAXN * MAXN) >> 1];
bool cmp( struct node r1, struct node r2 )
{
    return r1.c < r2.c;
}
int pre[MAXN];
void init()
{
    for( int i=0; i<MAXN; i++ )
        pre[i] = i;
}
int find( int x )
{
    int r = x;
    while( pre[r] != r )
        r = pre[r];
    int i = x, tmp;
    while( i != r )
    {
        tmp = pre[i];
        pre[i] = r;
        i = tmp;
    }
return r;
}
void join( int a, int b )
{
    int fa = find(a);
    int fb = find(b);
    if( fa != fb )
        pre[fa] = fb;
}

int main()
{
    int n, m;
    while( scanf("%d%d", &n, &m), n )
    {
        for( int i=0; i<n; i++ )
            scanf("%d%d%d", &road[i].a, &road[i].b, &road[i].c);
        sort(road, road+n, cmp);
        init();
        int sum = 0;
        int cnt = 0;
        int tmp1, tmp2;
        for( int i=0; i<n; i++ )
        {
            tmp1 = road[i].a;
            tmp2 = road[i].b;
            if( find(tmp1) != find(tmp2) )
            {
                join(tmp1, tmp2);
                sum += road[i].c;
                //cnt ++;
                //if( cnt == n-1 )
                //   break;
            }
        }
        set<int> s;
        s.clear();
        for( int i=1; i<=m; i++ )
        {
            int tmp = find(i);
            if( !s.count(tmp) )
                s.insert(tmp);
        }
        if( s.size() == 1 )
            printf("%d\n", sum);
        else
            printf("?\n");
    }




    return 0;
}