hdu6532(费用流)

|

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=6532

题意

给定一个$10^9\times10^9$ 的平面，平面上有 $n$ 个点，第 $i$ 个点的权值为 $i$ ，然后给出 $m$ 个限制 $(a,b)$ ，表示选中的 $x\ge a$ 或者 $y\ge a$ 的点数不大于 $y$ ，现选中尽可能多的点，使得满足上述限制的情况下权值最大

题解

对只有行的限制，可以将点往行连费用为 $i$ ，容量为 $1$ 的边

行之间相互连费用为 $0$ 的边，容量为当前行开始的最大点数

然后源点连向点跑费用流即可。。

现在有列的限制，而一个点无法流向两个，然后场上直接卡这了。。

其实只要让点对应的流量分别顺着行列流即可，又发现不一定非得从点流进流量，所以可以把点变成边，这样就能双向流流量，对应地列的连边方向也得倒过来，然后经过点从行流向列即可。。




代码

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
/**
 *　　　　　　  　　┏┓　　 　┏┓
 * 　　　　　  　　┏┛┗━━━━━━━┛┗━━━┓
 * 　　　　　  　　┃　　　　　　　┃ 　
 * 　　　　　  　　┃　　　━　　 　┃
 * 　　　　　  　　┃　＞　　　＜　┃
 * 　　　　　  　　┃　　　　　　　┃
 * 　　　　　  　　┃...　⌒　... 　┃
 * 　　　　　　  　┃              ┃
 * 　　　　　　  　┗━┓          ┏━┛
 * 　　　　　　　　　┃          ┃　Code is far away from bug with the animal protecting　　　　　　　　　　
 * 　　　　　　　　　┃          ┃   神兽保佑,代码无bug
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┃  　　　　　　
 * 　　　　　　　　　┃          ┃
 * 　　　　　　　　　┃          ┃　　　　　　　　　　　
 * 　　　　　　　　　┃          ┗━━━┓
 * 　　　　　　　　　┃              ┣┓
 * 　　　　　　　　　┃              ┏┛
 * 　　　　　　　　　┗┓┓┏━━━━━━━━┳┓┏┛
 * 　　　　　　　　　　┃┫┫       ┃┫┫
 * 　　　　　　　　　　┗┻┛       ┗┻┛
 */ 
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<set>
#include<bitset>
#include<complex>
#include<cstdlib>
#include<assert.h>
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,l,r) for(int i=l;i>=r;i--)
#define link(x) for(edge *j=h[x];j;j=j->next)
#define mem(a) memset(a,0,sizeof(a))
#define mid (x+y>>1)
#define ll long long
#define eps 1e-8
#define succ(x) (1<<x)
#define lowbit(x) (x&(-x))
#define sqr(x) ((x)*(x))
#define NM 1005
#define nm 10005
using namespace std;
const double pi=acos(-1);
const ll inf=1e9+7;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}

struct edge{int t,w,v;edge*next,*rev;}e[nm],*h[NM],*o=e,*p[NM];
void _add(int x,int y,int w,int v){o->v=v;o->w=w;o->t=y;o->next=h[x];h[x]=o++;}
void add(int x,int y,int w,int v){_add(x,y,w,v);_add(y,x,0,-v);h[x]->rev=h[y];h[y]->rev=h[x];}
int n,m,_x,_y,b[NM],c[NM],_b[NM],_c[NM],ans,tot,cnt;
int d[NM],w[NM];
bool v[NM];
queue<int>q;
char _s[5];


struct P{int x,y;}a[NM];

int spfa(){
    inc(i,0,n)d[i]=inf;mem(w);
    q.push(0);w[0]=inf;d[0]=0;v[0]++;
    while(!q.empty()){
	int t=q.front();q.pop();v[t]=false;
	link(t)if(j->w&&d[j->t]>d[t]+j->v){
	    d[j->t]=d[t]+j->v;p[j->t]=j;w[j->t]=min(w[t],j->w);
	    if(!v[j->t])q.push(j->t),v[j->t]++;
	}
    }
    return w[n];
}

int main(){
    n=read();
    inc(i,1,n)a[i].x=read(),a[i].y=read(),b[++tot]=a[i].x,c[++cnt]=a[i].y;
    sort(b+1,b+1+tot);tot=unique(b+1,b+1+tot)-b-1;
    sort(c+1,c+1+cnt);cnt=unique(c+1,c+1+cnt)-c-1;
    inc(i,1,n)a[i].x=lower_bound(b+1,b+1+tot,a[i].x)-b,a[i].y=lower_bound(c+1,c+1+cnt,a[i].y)-c;
    inc(i,1,tot)_b[i]=inf;
    inc(i,1,cnt)_c[i]=inf;
    m=read();while(m--){
	scanf("%s",_s);_x=read();_y=read();
	if(_s[0]=='R'){
	    _x=lower_bound(b+1,b+1+tot,_x)-b;
	    _b[_x]=min(_b[_x],_y);
	}else{
	    _x=lower_bound(c+1,c+1+cnt,_x)-c;
	    _c[_x]=min(_c[_x],_y);
	}
    }
    inc(i,2,tot)_b[i]=min(_b[i],_b[i-1]);
    inc(i,2,cnt)_c[i]=min(_c[i],_c[i-1]);
    //inc(i,1,tot)printf("%d ",_b[i]);putchar('\n');
    //inc(i,1,cnt)printf("%d ",_c[i]);putchar('\n');
    inc(i,1,tot)add(i-1,i,_b[i],0);
    inc(i,2,cnt)add(i+tot,i-1+tot,_c[i],0);
    add(tot+1,tot+cnt+1,_c[1],0);
    inc(i,1,n)add(a[i].x,tot+a[i].y,1,-i);
    n=tot+cnt+1;
    while(spfa()){
	ans-=w[n]*d[n];
	for(int x=n;x;x=p[x]->rev->t)p[x]->w-=w[n],p[x]->rev->w+=w[n];
    }
    return 0*printf("%d\n",ans);
}