UOJ#77. A+B Problem

题意：自己看

接触过线段树优化建图后思路不难想，细节要处理好

乱建图无果后想到最小割

白色和黑色只能选一个，割掉一个就行了

之前选白色必须额外割掉一个p[i]，i向i+n连p[i]，然后i+n向之前点连INF就行了

向一段区间连边？果断线段树优化

等等，还要满足\(l_i\le a_j \le r_i\)，权值建线段树，然后可持久化！

有一点细节没考虑好，就是之前的可能有x了这次a[i]=x，不需要重复把之前再连一遍，**只要新叶子到之前的叶子连INF就行了**

然后WA了一个小时，除了图上编号手残打错之外，一个主要的问题在于，可持久化线段树是动态开点，建树时父亲向孩子连边，不能在插入孩子的时候连边，有可能是之前的孩子，所以额外判断！！！

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define fir first

#define sec second

#define lc t[x].l

#define rc t[x].r

#define mid ((l+r)>>1)

#define lson lc, l, mid

#define rson rc, mid+1, r

typedef long long ll;

const int N=2e5+5, M=1e6+5, INF=1e9;

inline ll read(){

    char c=getchar();ll x=0,f=1;

    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

    return x*f;

}

int n, s, t, tot, mp[N], m, n2, b, w, p, sum;

struct meow{int a, l, r;}a[N];

struct edge{int v, c, f, ne;}e[M];

int cnt=1, h[N];

inline void ins(int u, int v, int c) { //printf("ins %d %d %d\n",u,v,c);

	e[++cnt]=(edge){v, c, 0, h[u]}; h[u]=cnt;

	e[++cnt]=(edge){u, 0, 0, h[v]}; h[v]=cnt;

}

namespace Flow{

	int q[N], head, tail, vis[N], d[N], cur[N];

	bool bfs(int s, int t) {

		memset(vis, 0, sizeof(vis));

		head=tail=1;

		q[tail++]=s; d[s]=0; vis[s]=1;

		while(head!=tail) {

			int u=q[head++];

			for(int i=h[u];i;i=e[i].ne)

				if(!vis[e[i].v] && e[i].c>e[i].f) {

					vis[e[i].v]=1; d[e[i].v]=d[u]+1;

					q[tail++]=e[i].v;

					if(e[i].v==t) return true;

				}

		}

		return false;

	}

	int dfs(int u, int a, int t) {

		if(u==t || a==0) return a;

		int flow=0, f;

		for(int &i=cur[u];i;i=e[i].ne)

			if(d[e[i].v]==d[u]+1 && (f=dfs(e[i].v, min(a, e[i].c-e[i].f), t))>0) {

				flow+=f;

				e[i].f+=f;

				e[i^1].f-=f;

				a-=f;

				if(a==0) break;

			}

		if(a) d[u]=-1;

		return flow;

	}

	int dinic(int s, int t) {

		int flow=0;

		while(bfs(s, t)) {

			for(int i=0; i<=tot; i++) cur[i]=h[i];

			flow+=dfs(s, INF, t); //printf("flow %d\n",flow);

		}

		return flow;

	}

}using Flow::dinic;

namespace Chair{

	struct meow{int l, r;}t[N];

	int sz, root[N];

	void insert(int &x, int l, int r, int val, int id) {

		int last=x;

		t[++sz]=t[x]; x=sz;

		if(l==r) {

			if(last) ins(n2+x, n2+last, INF);

			ins(n2+x, id, INF);

			return;

		}

		if(val<=mid) insert(lson, val, id);

		else insert(rson, val, id);

		if(lc) ins(n2+x, n2+lc, INF);

		if(rc) ins(n2+x, n2+rc, INF);

	}

	void rabit(int x, int l, int r, int ql, int qr, int u) {

		if(!x) return;

		if(ql<=l && r<=qr) ins(u, n2+x, INF);

		else {

			if(ql<=mid) rabit(lson, ql, qr, u);

			if(mid<qr ) rabit(rson, ql, qr, u);

		}

	}

	void build() {

		for(int i=1; i<=n; i++) root[i]=root[i-1], insert(root[i], 1, m, a[i].a, i);

		for(int i=2; i<=n; i++) rabit(root[i-1], 1, m, a[i].l, a[i].r, i+n);

		tot=sz+n2+1;

	}

}using Chair::build;

int main() {

	freopen("in","r",stdin);

	n=read(); s=0; t=N-1;

	n2=n*2;

	for(int i=1; i<=n; i++) {

		mp[++m]=a[i].a=read(), b=read(), w=read(), mp[++m]=a[i].l=read(), mp[++m]=a[i].r=read(), p=read();

		ins(s, i, b); ins(i, t, w); ins(i, i+n, p); sum+=b+w;

	}

	sort(mp+1, mp+1+m); m=unique(mp+1, mp+1+m)-mp-1;

	for(int i=1; i<=n; i++) {

		a[i].a = lower_bound(mp+1, mp+1+m, a[i].a)-mp;

		a[i].l = lower_bound(mp+1, mp+1+m, a[i].l)-mp;

		a[i].r = lower_bound(mp+1, mp+1+m, a[i].r)-mp;

	//	printf("hi %d   %d %d %d\n",i,a[i].a,a[i].l,a[i].r);

	}

	build();

	int ans=dinic(s, t); //printf("sum %d %d\n",sum,ans);

	printf("%d",sum-ans);

}

巴特西

UOJ#77. A+B Problem [可持久化线段树优化建边最小割]

UOJ#77. A+B Problem

最新文章

热门文章

巴特西

UOJ#77. A+B Problem [可持久化线段树优化建边 最小割]

UOJ#77. A+B Problem

最新文章

热门文章

UOJ#77. A+B Problem [可持久化线段树优化建边最小割]