【51nod】2564 格子染色
这道题原来是网络流……
感觉我网络流水平不行……
这种只有两种选择的可以源点向该点连一条容量为b的边，该点向汇点连一条容量为w的边，如果割掉了b证明选w，如果割掉了w证明选b
那么(p)的限制怎么加呢，新建一个点(i')，然后(i)往(i')流一条容量为(p)的边
(i')再向所有不合法的(j)连一条容量为正无穷的边，这样如果(i)选了(b)，(j)选了(w)，会有水流从(i ightarrow i' ightarrow j)
由于(n^2)的边太多了，我们用可持久化线段树优化建图可以改成(O(n log n))
最后的答案是每个点黑白价值的和减去最大流
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('
')
#define eps 1e-10
#define ba 47
#define MAXN 200005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 +c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct node {
int to,next,cap;
}E[MAXN * 10];
int head[MAXN],sumE = 1;
int N,S,T;
int dis[MAXN],Ncnt,cur[MAXN];
int a[5005],b[5005],w[5005],l[5005],r[5005],p[5005];
int val[5005],tot;
queue<int> Q;
void add(int u,int v,int c) {
E[++sumE].to = v;
E[sumE].cap = c;
E[sumE].next = head[u];
head[u] = sumE;
}
void addtwo(int u,int v,int c) {
add(u,v,c);add(v,u,0);
}
bool BFS() {
memset(dis,0,sizeof(dis));
while(!Q.empty()) Q.pop();
dis[S] = 1;
Q.push(S);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(!dis[v] && E[i].cap > 0) {
dis[v] = dis[u] + 1;
if(v == T) return true;
Q.push(v);
}
}
}
return false;
}
int dfs(int u,int aug) {
if(u == T) return aug;
for(int &i = cur[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(E[i].cap && dis[v] == dis[u] + 1) {
int t = dfs(v,min(aug,E[i].cap));
if(t) {
E[i].cap -= t;
E[i ^ 1].cap += t;
return t;
}
}
}
return 0;
}
int Dinic() {
int res = 0;
while(BFS()) {
for(int i = 1 ; i <= Ncnt ; ++i) cur[i] = head[i];
while(int d = dfs(S,0x7fffffff)) res += d;
}
return res;
}
int lc[MAXN],rc[MAXN],rt[5005],nw;
void Insert(int x,int &y,int l,int r,int pos,int v) {
y = ++Ncnt;
addtwo(y,x,2e9);
lc[y] = lc[x];rc[y] = rc[x];
if(l == r) {addtwo(y,v,2e9);return;}
int mid = (l + r) >> 1;
if(pos <= mid) {
Insert(lc[x],lc[y],l,mid,pos,v);
addtwo(y,lc[y],2e9);
}
else {
Insert(rc[x],rc[y],mid + 1,r,pos,v);
addtwo(y,rc[y],2e9);
}
}
void addE(int y,int l,int r,int ql,int qr) {
if(!y) return;
if(l == ql && qr == r) {addtwo(nw,y,2e9);return;}
int mid = (l + r) >> 1;
if(qr <= mid) addE(lc[y],l,mid,ql,qr);
else if(ql > mid) addE(rc[y],mid + 1,r,ql,qr);
else {addE(lc[y],l,mid,ql,mid);addE(rc[y],mid + 1,r,mid + 1,qr);}
}
void Solve() {
read(N);S = N + 1;T = N + 2;Ncnt = N + 2;
int res = 0;
for(int i = 1 ; i <= N ; ++i) {
read(a[i]);read(b[i]);read(w[i]);read(l[i]);read(r[i]);read(p[i]);
addtwo(S,i,b[i]);addtwo(i,T,w[i]);
res += w[i] + b[i];
val[++tot] = a[i];
}
sort(val + 1,val + tot + 1);
tot = unique(val + 1,val + tot + 1) - val - 1;
for(int i = 1 ; i <= N ; ++i) {
nw = ++Ncnt;
addtwo(i,nw,p[i]);
int s = lower_bound(val + 1,val + tot + 1,l[i]) - val;
int t = upper_bound(val + 1,val + tot + 1,r[i]) - val - 1;
if(s <= t) addE(rt[i - 1],1,tot,s,t);
s = lower_bound(val + 1,val + tot + 1,a[i]) - val;
Insert(rt[i - 1],rt[i],1,tot,s,i);
}
res -= Dinic();
out(res);enter;
}
int main(){
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
return 0;
}