[UOJ UNR#1]奇怪的线段树

来自FallDream的博客,未经允许,请勿转载, 谢谢。


原题可以到UOJ看,传送门

如果存在一个点是白的,却有儿子是黑的,显然无解。

不然的话,只要所有黑色的“黑叶子”节点,即没有黑色的儿子的节点有访问到就行了。

联想到今年CTSC上一道题叫“被操纵的线段树”,每个点被访问之后,可以和他合并的点满足左端点是它的右端点+1,并且和它没有相同的父亲。

发现这些点构成一条链,所以只需要向最大的那个点连边就行了,然后每个点向左儿子连边。

拆点之后,给所有的“黑色叶子”节点中间的边加上流量下界,求出最小流就是答案了。

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define S 0
#define T 16001
#define SS 16002
#define TT 16003
#define MN 16003
#define INF 2000000000
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int n,q[MN+],c[MN+],d[MN+],head[MN+],cnt=,Lt[MN+],Rt[MN+],dn=,m;
int in[MN+],L[MN+],R[MN+],s[MN+],ss[MN+],fa[MN+],top;
struct edge{int to,next,w;}e[MN*+];
vector<int> v[MN+]; inline void ins(int f,int t,int w)
{
e[++cnt]=(edge){t,head[f],w};head[f]=cnt;
e[++cnt]=(edge){f,head[t],};head[t]=cnt;
} int Build(int l,int r)
{
int x=++dn;s[x]=read();Lt[x]=l;Rt[x]=r;v[l].push_back(x);
if(l!=r)
{
int mid=read();
fa[L[x]=Build(l,mid)]=x;
fa[R[x]=Build(mid+,r)]=x;
ss[x]|=ss[L[x]]|ss[R[x]];
if(!s[x]&&ss[x]){puts("OwO");exit();}
ins(x,L[x],INF);
}
if(ss[x]|s[x]) ins(x,x+m,INF);
if(s[x]&&!ss[x]) ins(S,x,INF),--in[x],++in[x+m],ins(x+m,T,INF);
ss[x]|=s[x];return x;
} bool bfs()
{
memset(d,,sizeof(d));int i,j;
for(d[q[top=i=]=SS]=;i<=top;++i)
for(j=c[q[i]]=head[q[i]];j;j=e[j].next)
if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+;
return d[TT];
} int dfs(int x,int f)
{
if(x==TT) return f;int used=;
for(int&i=c[x];i;i=e[i].next)
if(e[i].w&&d[e[i].to]==d[x]+)
{
int w=dfs(e[i].to,min(f-used,e[i].w));
used+=w;e[i].w-=w;e[i^].w+=w;
if(used==f) return f;
}
return d[x]=-,used;
} int main()
{
n=read();m=*n-;Build(,n);
for(int i=,j,k;i<=dn;++i)
for(j=,k=Rt[i]+;j<v[k].size();++j)
if(v[k][j]!=R[fa[i]]) {ins(i+m,v[k][j],INF);break;}
for(int i=;i<=dn<<;++i) if(in[i]>) ins(SS,i,in[i]); else if(in[i]<) ins(i,TT,-in[i]);
while(bfs()) dfs(SS,INF);ins(T,S,INF);
while(bfs()) dfs(SS,INF);
printf("%d\n",e[cnt].w);
return ;
}
上一篇:C# windows application Hello World


下一篇:redis 数据备份持久化方案