Link
题意:
有n(n<=20000)个小球，最开始都未被染色。
进行m(m<=20000)次操作，操作分为2种类型。
0.回到第x次操作的状态
1.将小球x和y所在的集合合并
然后进行k(k<=20000)次染色操作。
第i次染色操作将时间ti时xi所在连通块中最多zi个小球染色。
如果一个小球被染色了，那么任意时刻它都被染色了。
求最多能将多少小球染色。
分析:
很容易想到网络流的做法，但是一般的建图方法的点数和边数都无法接受。
考虑用可持久化的思想优化网络流建图。
首先处理连通性时我们会用到用主席树实现的可持久化并查集。
注意，这时不能使用路径压缩，要按秩合并来优化。
然后可以发现可持久化并查集就可以来优化建图了。
我们只考虑叶子。
S向最初版本的每个叶子连容量1的边。
每次更新时将历史版本向当前版本连容量为+∞的边；
合并时，向集合代表元连容量为+∞的边。
每次染色时，找到ti版本xi所在集合的代表元，向T连容量为zi的边。
然后跑最大流就行了。
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 | #include <stdio.h>#include <string.h>#include <algorithm>#define S 1#define T 2#define inf 0x7f7f7f7f#define gap(i) e[i].c-e[i].fusing namespace std;#define g() getchar()template<class Q>void Scan(Q&x){ char c; while(c=g(),c<48||c>57); for(x=0;c>47&&c<58;c=g())x=10*x+c-48;}#define rep(i,a,b) for(int i=a;i<b;++i)const int MAXN=80005;int Id=2;typedef struct node*star;struct node{ int f,id,sz; star ch[2];}pool[MAXN*20];star tail=pool;inline star query(star x,int l,int r,int pos){ while(l<r){ int mid=(l+r)>>1,d=pos>mid; if(d)l=mid+1; else r=mid; x=x->ch[d]; } return x;}int n,m,k,Head[MAXN];star rt[MAXN];struct edge{ int t,c,f,n; edge(int t=0,int c=0,int n=0): t(t),c(c),f(0),n(n){}}e[MAXN<<2];int head[MAXN],tot=1;inline void AddEdge(int s,int t,int c=1){ e[++tot]=edge(t,c,head[s]),head[s]=tot; e[++tot]=edge(s,0,head[t]),head[t]=tot;}void build(star&x,int l,int r){ x=tail++; if(l==r){ x->f=l,x->sz=1; AddEdge(S,x->id=++Id); return; } int mid=(l+r)>>1; build(x->ch[0],l,mid); build(x->ch[1],mid+1,r);}void update(star&y,star x,int l,int r,int t,int f,int v){ y=++tail; *y=*x; if(l==r){ y->f=f,y->sz+=v; AddEdge(x->id,y->id=++Id,inf); return; } int mid=(l+r)>>1,d=t>mid; if(d)l=mid+1; else r=mid; update(y->ch[d],x->ch[d],l,r,t,f,v);}star find(int idx,int x){ star res=query(rt[idx],1,n,x); return res->f==x?res:find(idx,res->f);}inline void Init(){ Scan(n),Scan(m),Scan(k); build(rt[0],1,n);}inline void Merge(int idx,int x,int y){ star fx=find(idx,x); star fy=find(idx,y); if(fx->f==fy->f)return; if(fx->sz>fy->sz)swap(fx,fy); update(rt[idx],rt[idx],1,n,fx->f,fy->f,0); update(rt[idx],rt[idx],1,n,fy->f,fy->f,fx->sz); fx=query(rt[idx],1,n,fx->f); fy=query(rt[idx],1,n,fy->f); AddEdge(fx->id,fy->id,inf);}int d[MAXN],p[MAXN],q[MAXN];int cur[MAXN],g[MAXN];inline int isap(int s,int t,int n){ rep(i,1,n+1)d[i]=n; int tail=1; q[1]=t; d[t]=0; rep(h,1,tail+1){ int x=q[h]; ++g[d[x]],cur[x]=head[x]; for(int i=head[x],y;i;i=e[i].n) if(!e[i].c&&d[y=e[i].t]==n){ d[y]=d[x]+1; q[++tail]=y; } } int flow=0,x=s,a,f; while(d[s]<n){ if(x==t){ a=inf; for(int i=t;i!=s;i=e[p[i]^1].t) a=min(a,gap(p[i])); for(int i=t;i!=s;i=e[p[i]^1].t) e[p[i]].f+=a,e[p[i]^1].f-=a; flow+=a; x=s; } f=1; for(int&i=cur[x];i;i=e[i].n) if(gap(i)&&d[x]==d[e[i].t]+1){ f=0; p[x=e[i].t]=i; break; } if(f){ if(!(--g[d[x]]))break; f=n-1; for(int i=head[x];i;i=e[i].n) if(gap(i))f=min(f,d[e[i].t]); ++g[d[x]=f+1]; cur[x]=head[x]; if(x!=s)x=e[p[x]^1].t; } } return flow;}inline void Solve(){ rep(i,1,m+1){ rt[i]=rt[i-1]; int t,x,y; Scan(t),Scan(x); if(t)Scan(y),Merge(i,x,y); else rt[i]=rt[x]; } rep(i,0,k){ int x,y,w; Scan(x),Scan(y),Scan(w); star f=find(x,y); AddEdge(f->id,T,w); } printf("%d\n",isap(S,T,Id));}int main(){ freopen("link.in","r",stdin); freopen("link.out","w",stdout); Init(); Solve(); return 0;} |
评论 (0)
