UOJ 217 奇怪的线段树

http://uoj.ac/problem/217

题意就不X了,思路在这:
UOJ 217 奇怪的线段树

UOJ 217 奇怪的线段树

居然一开始把sap里面的mn设置为inf了,我是傻逼。。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
int go[],first[],next[],flow[],op[],dis[],cnt[];
int tot,S,T,t,s,sz,son[],du[],n,nodes;
bool flag;
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y,int z){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
flow[tot]=z;
}
void add(int x,int y,int z){
insert(x,y,z);op[tot]=tot+;
insert(y,x,);op[tot]=tot-;
}
void add(int x,int y,int low,int high){
int F=high-low;
add(x,y,F);du[x]-=low;du[y]+=low;
}
int build(int l,int r,int op){
int k=++sz;
add(s,k,,inf);add(k+*n-,t,,inf);
add(*n-+l,k,,inf);if (op&&r<n) add(k+*n-,*n-+r+,,inf);
if (!op) add(*n-+l,k,,inf);
if (!op&&r<n) add(k+*n-,*n-+r+,,inf);
int x=read();
if (l==r){
son[k]=x;
return x;
}
int mid=read();
int p=build(l,mid,),q=build(mid+,r,);
if (p||q){
if (!x) flag=;
son[k]=;
return ;
}
return son[k]=x;
}
int dfs(int x,int f){
if (x==T) return f;
int mn=nodes,sum=;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (dis[pur]+==dis[x]&&flow[i]){
int F=std::min(flow[i],f-sum);
int save=dfs(pur,F);
sum+=save;
flow[i]-=save;
flow[op[i]]+=save;
if (sum==f||dis[S]>=nodes) return sum;
}
if (flow[i]) mn=std::min(mn,dis[pur]);
}
if (sum==){
cnt[dis[x]]--;
if (cnt[dis[x]]==){
dis[S]=nodes;
}else{
dis[x]=mn+;
cnt[dis[x]]++;
}
}
return sum;
}
int mxflow(){
int res=,tim=;
while (dis[S]<nodes){
tim++;
res+=dfs(S,inf);
}
return res;
}
int main(){
n=read();
s=;t=*n-;
flag=;
build(,n,);
if (!flag) {puts("OwO");return ;}
for (int i=;i<=sz;i++)
if (son[i]==)
add(i,i+sz,,inf);
else
if (son[i]==)
add(i,i+sz,,inf);
S=t+,T=S+;nodes=T+;
for (int i=s;i<=t;i++)
if (du[i]>) add(S,i,du[i]);
else if (du[i]<) add(i,T,-du[i]);
int ans1=mxflow();
memset(dis,,sizeof dis);
memset(cnt,,sizeof cnt);
add(t,s,inf);
int ans=mxflow();
printf("%d\n",ans);
}
上一篇:【uoj#228】基础数据结构练习题 线段树+均摊分析


下一篇:js日期、月份:日期加一天等