[AGC031E] Snuke the Phantom Thief

标签：Phantom leq jewels Sample Snuke 坐标 steal AGC031E

Problem Statement

A museum exhibits $N$ jewels, Jewel $1, 2, ..., N$. The coordinates of Jewel $i$ are $(x_i, y_i)$ (the museum can be regarded as a two-dimensional plane), and the value of that jewel is $v_i$.

Snuke the thief will steal some of these jewels.

There are $M$ conditions, Condition $1, 2, ..., M$, that must be met when stealing jewels, or he will be caught by the detective. Each condition has one of the following four forms:

($t_i$ =L, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $x$ coordinates are $a_i$ or smaller.
($t_i$ =R, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $x$ coordinates are $a_i$ or larger.
($t_i$ =D, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $y$ coordinates are $a_i$ or smaller.
($t_i$ =U, $a_i$, $b_i$) : Snuke can only steal at most $b_i$ jewels whose $y$ coordinates are $a_i$ or larger.

Find the maximum sum of values of jewels that Snuke the thief can steal.

Constraints

$1 \leq N \leq 80$
$1 \leq x_i, y_i \leq 100$
$1 \leq v_i \leq 10^{15}$
$1 \leq M \leq 320$
$t_i$ is L, R, U or D.
$1 \leq a_i \leq 100$
$0 \leq b_i \leq N - 1$
$(x_i, y_i)$ are pairwise distinct.
$(t_i, a_i)$ are pairwise distinct.
$(t_i, b_i)$ are pairwise distinct.

Input

Input is given from Standard Input in the following format:

$N$
$x_1$ $y_1$ $v_1$
$x_2$ $y_2$ $v_2$
$:$
$x_N$ $y_N$ $v_N$
$M$
$t_1$ $a_1$ $b_1$
$t_2$ $a_2$ $b_2$
$:$
$t_M$ $a_M$ $b_M$

Output

Print the maximum sum of values of jewels that Snuke the thief can steal.

Sample Input 1

Sample Output 1

Stealing Jewel $1, 5, 6$ and $7$ results in the total value of $36$.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

10
66 47 71040136000
65 77 74799603000
80 53 91192869000
24 34 24931901000
91 78 49867703000
68 71 46108236000
46 73 74799603000
56 63 93122668000
32 51 71030136000
51 26 70912345000
21
L 51 1
L 7 0
U 47 4
R 92 0
R 91 1
D 53 2
R 65 3
D 13 0
U 63 3
L 68 3
D 47 1
L 91 5
R 32 4
L 66 2
L 80 4
D 77 4
U 73 1
D 78 5
U 26 5
R 80 2
R 24 5

Sample Output 4

305223377000

这个范围，基本上只要是多项式复杂度都能过得去了吧。

$x$ 坐标小于等于 $a_i$ 的至多有 $b_i$ 个，这个条件很不友好。我们把他转换一下，这其实说明如果将所有选了的宝石按照 $x$ 坐标从小到大排序，排名大于 $b_i$ 的，$x$ 坐标要大于 $a_i$。同理，坐标大于等于 $a_i$ 的至多有 $b_i$ 个的条件，我们可以转化成按 $x$ 坐标从小到大排序之后，倒数排名要大于 $b_i$ 的，$x$ 坐标要小于等于 $b_i$。$y$ 坐标同理。

这一个正着一个倒着的，怎么玩啊？反正 $n$ 小的离谱，我们可以枚举一下总共选多少个数，然后可以求出 $x$ 坐标排名为 $i$ 的数 $x$ 坐标的范围。$y$ 坐标同理。

在求出 $x$，$y$ 排名第 $i$ 的范围时，发现现在的问题转变为一个选数的问题，要给 $x$ 排名第 $i$ 的选一个坐标，然后还要给 $y$ 排名第 $i$ 的选一个坐标。这个问题就是经典的费用流模型了。

从源点连向表示 $x$ 排名为第 $i$ 个的点，流量1费用0，再从 $x$ 排名第 $i$ 个的点连向每个符合要求的坐标，流量1费用0。要把一个坐标拆成两个点，中间连流量1费用 $v_i$。如果他在 $y$ 坐标可以排名第 $i$，那么就从他连向表示 $y$ 坐标排名第 $i$ 的点，再连回汇点。

判断一下是否满流就行了。但我们想求最大费用，相当于取负后求最小费用，然后一起加一个 $10^{15}$ 避免负环。最后答案减去 $5\times i\times10^{15}$ 就行了，$i$ 为现在枚举到的选宝石个数。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INFLL=4e18,INFL=1e15+10;
const int N=505,T=N-1,S1=85,K=85,S2=170,S3=255,INF=2e9;
int hd[N],e_num(1),n,m,x[K],y[K],q[N*N*N],l,r,a[N],b[N],vhd[N],v[N],lx[K],ly[K],rx[K],ry[K],cnt;
char ch[N][5];
LL d[N],ret,ans,vv[N];
struct edge{
	int v,nxt,f;
	LL w;
}e[N*N*5];
void add_edge(int u,int v,int f,LL w)
{
	e[++e_num]=(edge){v,hd[u],f,INFL-w};
	hd[u]=e_num;
	e[++e_num]=(edge){u,hd[v],0,w-INFL};
	hd[v]=e_num;
}
int bfs()
{
	memset(d,0x7f,sizeof(d));
	memcpy(hd,vhd,sizeof(hd));
	v[d[q[l=r=1]=0]=0]=1;
	while(l<=r)
	{
//		printf("%d\n",q[l%N]);
		for(int i=hd[q[l]];i;i=e[i].nxt)
		{
//			printf("%d\n",e[i].v);
			if(d[e[i].v]>d[q[l]]+e[i].w&&e[i].f)
			{
				d[e[i].v]=d[q[l]]+e[i].w;
				if(!v[e[i].v])
				{
					++r;
					v[e[i].v]=1,q[r]=e[i].v;
				}
			}
		}
		v[q[l]]=0;
		++l;
	}
//	printf("%lld\n",d[T]);,
	return d[T]<INFLL;
}
int dfs(int x,int s)
{
	if(x==T)
		return s;
	v[x]=1;
	int g;
//	printf("%d %d\n",x,s);
	for(int&i=hd[x];i;i=e[i].nxt)
	{
		if(!v[e[i].v]&&e[i].f&&d[e[i].v]==d[x]+e[i].w&&(g=dfs(e[i].v,min(s,e[i].f))))
		{
			e[i].f-=g;
			e[i^1].f+=g;
			ans+=e[i].w*g;
			v[x]=0;
			return g;
		}
	}
	v[x]=0;
	return 0;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d%lld",x+i,y+i,vv+i);
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
		scanf("%s%d%d",ch[i],a+i,b+i);
 	for(int i=1;i<=n;i++)//枚举选多少个珠宝
	{
//		printf("%d\n",i);
		e_num=1;
		memset(hd,0,sizeof(hd));
		memset(lx,0,sizeof(lx));
		memset(rx,0x7f,sizeof(rx));
		memset(ly,0,sizeof(ly));
		memset(ry,0x7f,sizeof(ry));
		for(int j=1;j<=n;j++)
			add_edge(S2+j,S3+j,1,vv[j]);
		for(int j=1;j<=i;j++)
		{
			add_edge(0,j,1,0);
			add_edge(j+S1,T,1,0);
		}
		for(int j=1;j<=m;j++)
		{
			if(ch[j][0]=='L') 
				for(int k=b[j]+1;k<=i;k++)
					lx[k]=max(lx[k],a[j]+1);
			if(ch[j][0]=='R')
				for(int k=1;k<=i-b[j];k++)
					rx[k]=min(rx[k],a[j]-1);
			if(ch[j][0]=='D') 
				for(int k=b[j]+1;k<=i;k++)
					ly[k]=max(ly[k],a[j]+1);
			if(ch[j][0]=='U')
				for(int k=1;k<=i-b[j];k++)
					ry[k]=min(ry[k],a[j]-1);
		}
//		for(int j=1;j<=i;j++)
//			printf("%d %d %d %d\n",lx[j],rx[j],ly[j],ry[j]);
//		puts("");
		for(int j=1;j<=i;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(lx[j]<=x[k]&&x[k]<=rx[j])
					add_edge(j,k+S2,1,0);
				if(ly[j]<=y[k]&&y[k]<=ry[j])
					add_edge(k+S3,j+S1,1,0);
			}
		}
		ans=cnt=0;
		memcpy(vhd,hd,sizeof(vhd));
		int kk;
		while(bfs())
			while(kk=dfs(0,INF))
				cnt+=kk;
		if(cnt==i)
			ret=max(ret,i*INFL*5-ans);
	} 
	printf("%lld",ret);
}

标签：Phantom,leq,jewels,Sample,Snuke,坐标,steal,AGC031E
From： https://www.cnblogs.com/mekoszc/p/17065231.html