（最小生成树）NOJ-2301

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 4 测试通过 : 2
比赛描述

oo吃饱了想跟饥饿的你玩一个游戏。你们面前的桌子上有n个碗排成一行，编号为1,2,…,n，其中某些碗底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得由oo赠送的零食。你也可以贿赂oo，花费c_ij元，oo就会告诉你碗i,i+1,…,j这一段里球的总数的奇偶性。 你很好奇oo都准备了哪些零食。如果你采取了最优的询问策略，你至少需要花费多少元，才能保证拿到oo的所有奖励？

输入

ToDo

第一行一个整数T(1<=T<=10)表示case的数量 对于每个case，第一行一个整数n(1<=n<=400)，表示碗的数量。 下面n行，对于第i行，j从i开始。 比如 1 2 3 表示1-1花费1，1-2花费2，2-2花费3。 每行有n-i+1个整数，第i行第j个数表示询问i,i+1….j需要的花费。(1<=i<=j<=n,1<=c_ij<=10^9)

输出

每个case输出一个整数，表示最小花费

样例输入

1
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1

样例输出

7
题解：样例和题目好像都有毛病…不过就是一个最小生成树，这样可以以最小的权值知道所有的信息
用的是K树，即用并查集实现的最小边加边法

/*
  ID: oodt
  PROG:
  LANG:C++
*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<cassert>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<set>

using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

const int maxx=2005;
const int INF = 0x3f3f3f3f;
int n,m,k;
int c[maxx][maxx];
int vis[maxx];
int ans = 0,cnt = 0,pos = 0;
int l = 0,r = 0;

const int MAXN = 2010; 
const int MAXM = 4000200;
int F[MAXN]; 
struct Edge
{
    int u,v,w;
}edge[MAXM];
int tol;
void addedge(int u,int v,int w)
{
    edge[tol].u = u;
    edge[tol].v = v;
    edge[tol++].w = w;
}
bool cmp(Edge a,Edge b)
{ 
    return a.w<b.w;
}
int find(int x)
{
    if(F[x] == -1) return x;
    else return F[x] = find(F[x]);
}
ll kruskal(int n)
{
    memset(F,-1,sizeof(F));
    sort(edge,edge+tol,cmp);
    int cnt = 0;
    ll ans = 0;
    for(int i = 0; i < tol; i++)
    {
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;
        int t1 = find(u);
        int t2 = find(v);
        if(t1 != t2)
        {
            ans += w;
            F[t1] = t2;
            cnt ++;
        }
        if(cnt == n-1) break;
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        tol = 0;
        scanf("%d",&n);
        rep(i,0,n){
            rep(j,i+1,n+1){
                scanf("%d",&c[i][j]);
				addedge(i,j,c[i][j]);
            }
        }
        ll ans = kruskal(n+1);
        printf("%I64\n",ans);
    }
    return 0;
}