BZOJ 3714 Kuglarz
非常玄学的一道题....到现在还没理解为什么是最小生成树的题...
这里就从另一个角度解析题目，首先题目中每个杯子中是否藏有球可以视为0/1，而我们询问的一个区间的奇偶可以看做是若干个变量相异或的和，而每个变量的意义就是该杯子下是否藏有求0/1.那么我们的目的是想知道这n个变量的值，根据线性代数的一些知识，我们知道解出n个变量的唯一解的冲要条件是有n个本质上不同的方程(其实这也可以通过手玩样例来得出)。那我们怎么来选出这n个方程，并且维护他们是否已经被已有的方程给生成了。我们可以举个例子就能简单的判断，第一个方程：l-mid，第二个方程mid+1，r，第三个方程，l，r。显然第三个方程可以被前两个方程相加得到。维护关系的话我们很容易想到的就在边界处两边，可直接在l-mid，和mid+1-r连边，无法看出l和r的关系。同时我们发现只有相邻的时候才会合并，那我们将l-mid+1连边，mid+1-r连边即可。这样的话l-r就联通，说明l-r这个区间就不行了。那我们知道最后n个方程，即n个边最后的结果就是1到n+1的一个最小生成树。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2010;
int n,f[N],num;
struct wy{int x,y,v;}a[N*N*2];
inline int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
inline bool cmp(wy a,wy b){return a.v<b.v;}
inline void kruskal()
{
sort(a+1,a+num+1,cmp);
for(int i=1;i<=n+1;++i) f[i]=i;
int cnt=0;
ll ans=0;
for(int i=1;i<=num;++i)
{
int t1=getf(a[i].x),t2=getf(a[i].y);
if(t1!=t2)
{
f[t1]=t2;
ans+=a[i].v;
if(++cnt==n) break;
}
}
printf("%lld",ans);
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)
{
int x;scanf("%d",&x);
a[++num].x=i;a[num].y=j+1;
a[num].v=x;
}
kruskal();
return 0;
}