BZOJ 3714 Kuglarz

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;
} 
上一篇:b_wy_奥运会真实排名(拓扑排序)


下一篇:实验三 Linux系统用户管理及VIM配置