• 欢迎光临~

BZOJ3714

5

7

# 题意

[f_{i,j}=left(sum_{x=i}^js_xright)&1 ]

# 总结

1. (forall 1<ileq j leq n)，建立一条((s=i-1,t=j,w=c_{i,j]}))的无向边
2. (0)为根，跑最小生成树。
3. 最小生成树的边权和就是答案
``````#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>

long long unsigned n,tmp;
struct Edge
{
long long unsigned u,v,w;
}edge[8000021];
inline void add(long long unsigned a,long long unsigned b,long long unsigned c)
{
static long long unsigned tot=0;
}

long long unsigned mst()
{
long long unsigned dis[2011],res=0;
bool vis[2011];
std::memset(vis,0x00,sizeof(vis));
std::memset(dis,0x7f,sizeof(dis));
std::priority_queue<long long unsigned,std::vector<std::pair<long long unsigned,long long unsigned> >,std::greater<std::pair<long long unsigned,long long unsigned> > > q;
q.push(std::make_pair(0,0));
while(not q.empty())
{
long long unsigned i=q.top().second, tmp=q.top().first; q.pop(); if(vis[i]) continue;
vis[i]=true; res+=tmp;
{
if(dis[edge[j].v]>edge[j].w) q.push(std::make_pair(dis[edge[j].v]=edge[j].w,edge[j].v));
}
}
return res;
}

int main()
{
scanf("%llu",&n);
for(register long long unsigned i=1;i<=n;++i)
{
for(register long long unsigned j=i;j<=n;++j)
{
scanf("%llu",&tmp);