摘要:生成树模型转化

「PA2014」Kuglarz

题面

题目分析

给出了部分和关系,可以考虑转化成前缀和关系来做.

也就是设每个位置藏球数量的前缀和奇偶性为$f_i$,那么确定所有藏球的情况必须要确定所有$f_i$才行.

那么对于一次询问$(i,j)$,相当于确定了$f_{i-1}$和$f_j$的关系(异或),已知一个就可以推出另一个.

又因为我们已知$f_0$的奇偶性,所以只要将每一个询问进行连边,建出的生成树就可以推出所有$f_i$了.

求得的最小生成树的权值和即为答案.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=2010;
lxl n,EdgeSize,ans,ConCnt;
lxl fa[big];
struct _Edge
{
lxl u,v,w;
inline bool operator <(const _Edge &another)const
{
return w<another.w;
}
}e[big*big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
lxl find(lxl x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(void)
{
n=read();
for(R int i(0);i<=n;fa[i]=i,++i);
for(R int i(1);i<=n;++i)
for(R int j(i);j<=n;++j)
{
lxl w=read();
e[++EdgeSize]=(_Edge){i-1,j,w};
}
std::sort(e+1,e+1+EdgeSize);
for(R int i(1);i<=EdgeSize;++i)
{
lxl x=e[i].u,y=e[i].v,w=e[i].w;
lxl fax=find(x),fay=find(y);
if(fax!=fay)
{
fa[fax]=fay,ans+=w;
if(++ConCnt==n)break;
}
}
printf("%lld\n",ans);
return 0;
}