「AGC031E」 Snuke the Phantom Thief 题解
「AGC031E」Snuke the Phantom Thief
题意
\(~~~~\) \(n\) 颗珠宝，有坐标 \((x_i,y_i)\) 和价值 \(val_i\) ，同时还有 \(m\) 条限制，每条限制规定在某条水平/竖直线某一侧最多能取多少珠宝，求能取珠宝的最大价值。
\(~~~~\) \(1\leq n\leq 80,1\leq m\leq 320\).
题解
\(~~~~\) 输在了第一步的网络流，看完题解豁然开朗的网络流。
\(~~~~\) 首先注意到 \(n,m\) 很小，贪心、DP之类也不可做，那就考虑网络流。
\(~~~~\) 然后就是上文提到的输在第一步：枚举最终取了多少颗珠宝，将这个值记为 \(k\)。这么做是因为这道题不适合用流量去满足 \(m\) 条限制。
\(~~~~\) 那考虑对于每条限制：假设规定横坐标 \(\leq a_i\) 的珠宝最多取 \(b_i\) 个，那不就等价于横坐标 \(>a_i\) 的珠宝最少取 \(k-b_i\) 个吗？那人为使选择的珠宝按横坐标升序排序，这样就可以确定每个珠宝的横坐标范围，同理也可以确定纵坐标，注意这里不需要保证横坐标和纵坐标要绑定在同一珠宝上。
\(~~~~\) 注意到还有每个宝石只能选一次的限制，那么就将每个实际宝石的点拆成入和出，中间连一条 \(\text{Flow}=1,\text{Cost}=val_i\) 的边。
\(~~~~\) 然后建图：从源点向代表横坐标的选择宝石连 \(\text{Flow}=1,\text{Cost}=0\) 的边（以下简记为 \((1,0)\)），然后从代表横坐标的选择宝石向符合要求的实际宝石的入点连 \((1,0)\) ，符合要求的实际宝石的出点向代表纵坐标的选择宝石连边。最后跑最大费用最大流即可。由于会优先保证 \(\text{Flow}\) 最大 ，所以一定会选出 \(\leq k\) 块宝石，其中 \(
代码
查看代码
#include
#include
#include
#include
#define ll long long
using namespace std;
templatevoid read(T &x)
{
T f=1;x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9') {x=x*10+s-'0';s=getchar();}
x*=f;
}
struct Node{
ll x,y,val,id;
Node(){}
Node(ll X,ll Y,ll Val,ll ID){x=X,y=Y,val=Val,id=ID;}
}Jew[85];
struct Limit{
ll op,a,b;
Limit(){}
Limit(ll Op,ll A,ll B){op=Op,a=A,b=B;}
}Lim1[355],Lim2[355];
ll n,m;char op[1000];
ll Turn[300],cnt1,cnt2,L[85],R[85],U[85],D[85];
ll s,t,head[100005],to[1000005],nxt[1000005],W[1000005],Edgecnt;
ll Cost[1000005];
void AddEdge(ll a,ll b,ll c,ll d)
{
// printf("%lld %lld,Flow=%lld,Cost=%lld\n",a,b,c,d);
to[Edgecnt]=b; nxt[Edgecnt]=head[a]; W[Edgecnt]=c; Cost[Edgecnt]=d; head[a]=Edgecnt++;
to[Edgecnt]=a; nxt[Edgecnt]=head[b]; W[Edgecnt]=0; Cost[Edgecnt]=-d;head[b]=Edgecnt++;
}
ll pre[100005],Flow[100005],Inqueue[100005];
ll Dis[100005];
ll SPFA()
{
queueq;
for(ll i=1;i<=t;i++) Flow[i]=0,Dis[i]=-1e18,Inqueue[i]=0,pre[i]=-1;
q.push(s); Dis[s]=0; Flow[s]=1e18; pre[s]=0;
while(!q.empty())
{
ll u=q.front();q.pop();
Inqueue[u]=false;
for(ll i=head[u];~i;i=nxt[i])
{
ll v=to[i];
if(!W[i]||Dis[v]>=Dis[u]+Cost[i]) continue;
Dis[v]=Dis[u]+Cost[i]; Flow[v]=min(Flow[u],W[i]);
pre[v]=i;
if(!Inqueue[v]){q.push(v),Inqueue[v]=true;}
}
}
if(Dis[t]==-1e18) return 0;
return Flow[t];
}
ll CMFM()
{
ll tmp=0;ll ret=0;
while((tmp=SPFA()))
{
ret+=1ll*Dis[t]*tmp;
ll x=t;
while(x!=s)
{
W[pre[x]]-=tmp,W[pre[x]^1]+=tmp;x=to[pre[x]^1];
}
}
return ret;
}
ll Solve(ll k)
{
memset(head,-1,sizeof(head)); Edgecnt=0;
memset(L,128,sizeof(L)); memset(D,128,sizeof(D));
memset(R,127,sizeof(R)); memset(U,127,sizeof(U));
s=2*(k+n)+1;t=s+1;
// sort(Jew+1,Jew+1+n);
for(ll i=1;i<=k;i++) AddEdge(s,i,1,0),AddEdge(i+k+2*n,t,1,0);
for(ll i=1;i<=n;i++) AddEdge(k+Jew[i].id,k+n+Jew[i].id,1,Jew[i].val);
for(ll i=1;i<=cnt1;i++)
{
ll p=Lim1[i].b;
if(Lim1[i].op==1)//左边至多 p 个 => 右边至少 k-p 个 =>后 k-p 个的左端点必定 > a_i
for(ll j=k;j>=p+1;j--) L[j]=max(Lim1[i].a+1,L[j]);
else //同上，前 k-p 个右端点 < a_i
for(ll j=1;j<=k-p;j++) R[j]=min(Lim1[i].a-1,R[j]);
}
for(ll i=1;i<=cnt2;i++)
{
ll p=Lim2[i].b;
if(Lim2[i].op==1)
for(ll j=k;j>=k-(k-p)+1;j--) D[j]=max(Lim2[i].a+1,D[j]);
else
for(ll j=1;j<=k-p;j++) U[j]=min(Lim2[i].a-1,U[j]);
}
for(ll i=1;i<=k;i++)
{
for(ll j=1;j<=n;j++)
{
if(L[i]<=Jew[j].x&&Jew[j].x<=R[i]) AddEdge(i,k+j,1,0);
if(D[i]<=Jew[j].y&&Jew[j].y<=U[i]) AddEdge(k+n+j,k+2*n+i,1,0);
}
}
// puts("===");
return CMFM();
}
int main() {
read(n);ll val;
for(ll i=1,x,y;i<=n;i++)
{
read(x); read(y); read(val);
Jew[i]=Node(x,y,val,i);
}
read(m);
Turn['L']=1; Turn['R']=2;
Turn['D']=1; Turn['U']=2;
for(ll i=1,a,b;i<=m;i++)
{
scanf("%s",op+1); read(a); read(b);
if(op[1]=='L'||op[1]=='R') Lim1[++cnt1]=Limit(Turn[(int)op[1]],a,b);
else Lim2[++cnt2]=Limit(Turn[(int)op[1]],a,b);
}
ll Ans=0;
for(ll k=1;k<=n;k++)
Ans=max(Ans,Solve(k));
printf("%lld",Ans);
return 0;
}