描述 Description
魔术师的桌子上有 n 个杯子排成一行，编号为 1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费 c_ij 元，魔术师就会告诉你杯子 i,i+1,…,j 底下藏有球的总数的奇偶性。
采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？
输入格式 InputFormat
第一行一个整数 n(1<=n<=2000)。
第 i+1 行 (1<=i<=n) 有 n+1-i 个整数，表示每一种询问所需的花费。其中 c_ij（对区间 [i,j] 进行询问的费用，1<=i<=j<=n,1<=c_ij<=10^9）为第 i+1 行第 j+1-i 个数。
输出格式 OutputFormat
输出一个整数，表示最少花费。
样例输入 SampleInput
5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
样例输出 SampleOutput
7
来源 Source
鸣谢 Jcvb
代码 Code
给出 [i,j] 的奇偶性即为已知 sum[i-1]和 sum[j]的奇偶性（sum[]为前缀和），那么为了得出每个杯子下是否藏球即必须得到所有的前缀和，即所有点互相连通，即为求最小生成树。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int x,y,z;
bool operator < (const edge& tmp) const
{
return (z!=tmp.z)?(z<tmp.z):((x!=tmp.x)?(x<tmp.x):(y<tmp.y));
}
};
vector <edge> e;
int fa[2005];
long long ans;
int getfa(int s)
{
if (fa[s]==s) return s;
fa[s]=getfa(fa[s]);
return fa[s];
}
int main()
{
e.clear();
scanf("%d",&n);
for (i=1;i<=n;i++) fa[i]=i;
for (i=1;i<=n;i++) for (j=i;j<=n;j++)
{
scanf("%d",&t);
e.push_back((edge){i-1,j,t});
}
sort(e.begin(),e.end());
ans=0;
for (i=0;i<e.size();i++) if (getfa(e[i].x)!=getfa(e[i].y))
{
fa[getfa(e[i].x)]=e[i].y;
ans+=e[i].z;
}
printf("%lld",ans);
return 0;
}