Description：

一排杯子下有一些球，付出 $c[i][j]$ 的代价能知道 $i$ 到 $j$ 的杯子下球的个数和的奇偶性，问最少付出多少代价使得确定每个杯子下是否有球。

$1\le n \le 2000$

Solution：

如果付出 $c[i][j]$ 的代价相当于是知道了 $sum[j]-sum[i-1]$ 的奇偶性，而 $sum[0]$ 的奇偶性是已知的，这启示我们可以连一条 $i-1\longleftrightarrow j$ 边权为 $c[i][j]$ 的边，那么一个联通块中只要有一个点奇偶性确定，其他所有点就都确定了，所以最小生成树。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 2010

struct edge

{

    int u,v,w;

}e[MAXN * MAXN];

int edgenum = 0;

void add(int a,int b,int c)

{

    ++edgenum;e[edgenum].u = a;e[edgenum].v = b;e[edgenum].w = c;

    return;

}

bool cmp(edge a,edge b){return a.w < b.w;}

int f[MAXN];

int find(int x){return (f[x] == -1 ? x : f[x] = find(f[x]));}

int main()

{

    scanf("%d",&n);

    int k;

    for(int i = 1;i <= n;++i)

    {

        for(int j = i;j <= n;++j)

        {

            scanf("%d",&k);

            add(i - 1,j,k);

        }

    }

    memset(f,-1,sizeof(f));

    sort(e + 1,e + 1 + edgenum,cmp);

    long long ans = 0;

    for(int i = 1;i <= edgenum;++i)

    {

        if(find(e[i].u) != find(e[i].v))

        {

            f[find(e[i].u)] = find(e[i].v);

            ans += e[i].w;

        }

    }

    cout << ans << endl;

    return 0;

}