AGC031ESnukethePhantomThief

Link
枚举偷了几个珠宝，然后求出按横/纵坐标升序排序之后第\(i\)个珠宝的合法横/纵坐标范围。
每个珠宝拆成入点出点，入点到出点有一条流量为\(1\)费用为价值的边。
然后再建\(k\)个坐标出/入点，分别和源/汇点连边，其中第\(i\)个出/入点代表按按横/纵坐标升序排序之后的第\(i\)个珠宝，它和横/纵坐标在该范围内的入/出点连边。这些边都是流量为\(1\)费用为\(0\)。
那么我们会建出一个源点\(\rightarrow\)坐标出点\(\rightarrow\)珠宝入点\(\rightarrow\)珠宝出点\(\rightarrow\)坐标入点\(\rightarrow\)汇点的分层图，求最大费用最大流就行了。

#include
#include
#include
#include
using i64=long long;
const int V=327,E=26087;const i64 inf=1e18;
int n,m,s,t,tot,head[V],vis[V];i64 cost,dis[V];
struct edge{int v,f;i64 c;int next;}e[E];
struct node{int x,y;i64 v;}p[V];
struct opt{int o,a,b;}op[V];
int read(){int x=0;int c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
i64 raed(){i64 x=0;int c=getchar();while(isspace(c))c=getchar();while(isdigit(c))(x*=10)+=c&15,c=getchar();return x;}
void add(int u,int v,int f,i64 c){e[++tot]={v,f,c,head[u]},head[u]=tot,e[++tot]={u,0,-c,head[v]},head[v]=tot;}
int update()
{
i64 mn=inf;
for(int u=1;u<=t;++u) if(vis[u]) for(int i=head[u];i;i=e[i].next) if(!vis[e[i].v]&&e[i].f) mn=std::min(mn,dis[e[i].v]+e[i].c-dis[u]);
if(mn==inf) return 0;
for(int u=1;u<=t;++u) if(vis[u]) dis[u]+=mn;
return 1;
}
int dfs(int u,int res)
{
if(u==t) return cost-=dis[s]*res,res;
int use=0;vis[u]=1;
for(int i=head[u],t;i;i=e[i].next)
if(!vis[e[i].v]&&e[i].f&&dis[u]==dis[e[i].v]+e[i].c)
{
t=dfs(e[i].v,std::min(res-use,e[i].f)),use+=t,e[i].f-=t,e[i^1].f+=t;
if(use==res) return use;
}
return use;
}
void solve(int k)
{
static int lx[V],rx[V],ly[V],ry[V];
tot=1,cost=0,s=2*k+2*n+1,t=s+1,memset(head+1,0,t<<2),memset(dis+1,0,t<<3);
memset(lx+1,0,k<<2),memset(ly+1,0,k<<2),memset(rx+1,0x7f,k<<2),memset(ry+1,0x7f,k<<2);
for(int i=1;i<=k;++i) add(s,i,1,0),add(i+n+n+k,t,1,0);
for(int i=1;i<=n;++i) add(i+k,i+n+k,1,-p[i].v);
for(int i=1;i<=m;++i)
switch(op[i].o)
{
case‘U‘:for(int j=1;j<=k-op[i].b;++j)ry[j]=std::min(ry[j],op[i].a-1);break;
case‘D‘:for(int j=op[i].b+1;j<=k;++j)ly[j]=std::max(ly[j],op[i].a+1);break;
case‘L‘:for(int j=op[i].b+1;j<=k;++j)lx[j]=std::max(lx[j],op[i].a+1);break;
case‘R‘:for(int j=1;j<=k-op[i].b;++j)rx[j]=std::min(rx[j],op[i].a-1);break;
}
for(int i=1;i<=k;++i) for(int j=1;j<=n;++j) if(lx[i]<=p[j].x&&p[j].x<=rx[i]) add(i,j+k,1,0);
for(int i=1;i<=k;++i) for(int j=1;j<=n;++j) if(ly[i]<=p[j].y&&p[j].y<=ry[i]) add(j+n+k,i+n+n+k,1,0);
do do memset(vis+1,0,t<<2);while(dfs(s,1e9));while(update());
}
int main()
{
i64 ans=0;
n=read();for(int i=1;i<=n;++i) p[i]={read(),read(),raed()};
m=read();for(int i=1;i<=m;++i) op[i]={getchar(),read(),read()};
for(int k=1;k<=n;++k) solve(k),ans=std::max(ans,cost);
printf("%lld",ans);
}