题解：P12463 [Ynoi Easy Round 2018] 星野瑠美衣

littlez_meow · 2025-06-02 16:57:36 · 题解

下面认为 x_{n+1}=x_1,y_{n+1}=y_1 以及 n,m 同阶。

先来研究 y 全部相等的情况。

数轴上我们把权值为 v 的 x 插入到 x_1,x_2 之间，则总权值有如下几种变化量：

当 x<\min\{x_1,x_2\}，变化量为 -|x_1-x_2|+x_1+x_2-2x+v；
当 \min\{x_1,x_2\}\le x\le \max\{x_1,x_2\}，变化量为 v；
当 x>\max\{x_1,x_2\}，变化量为 -|x_1-x_2|-x_1-x_2+2x+v。

画图发现，我们可以不管前提条件，直接对这三个式子取 \max 就可以得到最大值。

再加上 y 的贡献，一共就是 9 种情况。

那么就可以进行费用流建模了。

我们一共有五类点：源点 S、汇点 T、代表 m 个点的 A_1,\cdots,A_m、代表可插入的 n 个空位的 B_1,\cdots,B_n、计算权值的虚点 C_1,\cdots,C_9。

有如下四类容量均为 1 的边：

点数边数都是 O(n)，没有正环。直接跑最大费用最大流即可，时间复杂度 O(n^3)。

直接费用流跑不过去，考虑模拟费用流，我们每次找一条增广路。

这张图是二分图，左部点有 S,T,C_1,\cdots,C_9 一共 11 个，剩下的是右部点。增广时我们会找一条从 S 到 T 的路径，由于是二分图，路径必然是左部点右部点交错，因此长度是 O(1) 的。

那么直接维护任意两个左部点之间经过一个右部点的最长路，以这个为边权在左部点内部跑 SPFA，找出来增广路后暴力修改影响到的路径。我们维护任意两个左部点之间经过一个右部点的所有路径，每次增广是把 O(1) 条边反转了，相当于是删除 O(1) 条路径再加入 O(1) 条，使用可删堆维护即可。

时间复杂度 O(n\log n)。

代码

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define fi first
#define se second
using namespace std;
const int MAXN=2e5+1;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,px[MAXN],py[MAXN],x[MAXN],y[MAXN],v[MAXN];
//S->0,T->10
priority_queue<pair<ll,int> >q[11][11],del[11][11];
ll ans,val[11][MAXN],dis[11][11],dep[11];
int dir[11][MAXN],fr[11];
inline void era(int u,int mid,int v){
    F(i,0,10) if(dir[i][mid]*dir[u][mid]==-1){
        if(dir[u][mid]==1) del[u][i].emplace(val[u][mid]+val[i][mid],mid);
        else del[i][u].emplace(val[u][mid]+val[i][mid],mid);
    }
    F(i,0,10) if(i!=u&&dir[i][mid]*dir[v][mid]==-1){
        if(dir[v][mid]==-1) del[i][v].emplace(val[v][mid]+val[i][mid],mid);
        else del[v][i].emplace(val[v][mid]+val[i][mid],mid);
    }
}
inline void add(int u,int mid,int v){
    F(i,0,10) if(dir[i][mid]*dir[v][mid]==-1){
        if(dir[v][mid]==1) q[v][i].emplace(val[v][mid]+val[i][mid],mid);
        else q[i][v].emplace(val[v][mid]+val[i][mid],mid);
    }
    F(i,0,10) if(i!=v&&dir[i][mid]*dir[u][mid]==-1){
        if(dir[u][mid]==-1) q[i][u].emplace(val[u][mid]+val[i][mid],mid);
        else q[u][i].emplace(val[u][mid]+val[i][mid],mid);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    F(i,1,n) cin>>px[i]>>py[i];
    px[n+1]=px[1],py[n+1]=py[1];
    F(i,1,m) cin>>x[i]>>y[i]>>v[i];
    F(i,1,m){
        val[0][i]=v[i],dir[0][i]=1;
        val[10][i]=-INF;
        F(j,1,9){
            dir[j][i]=-1;
            switch((j-1)/3){
                case 0:{val[j][i]-=2*x[i];break;}
                case 2:{val[j][i]+=2*x[i];break;}
            }
            switch(j%3){
                case 1:{val[j][i]-=2*y[i];break;}
                case 0:{val[j][i]+=2*y[i];break;}
            }
        }
    }
    F(i,1,n){
        val[0][i+m]=-INF;
        val[10][i+m]=-abs(px[i]-px[i+1])-abs(py[i]-py[i+1]),dir[10][i+m]=-1;
        F(j,1,9){
            dir[j][i+m]=1;
            switch((j-1)/3){
                case 0:{val[j][i+m]+=px[i]+px[i+1];break;}
                case 1:{val[j][i+m]+=abs(px[i]-px[i+1]);break;}
                case 2:{val[j][i+m]+=-px[i]-px[i+1];break;}
            }
            switch(j%3){
                case 1:{val[j][i+m]+=py[i]+py[i+1];break;}
                case 2:{val[j][i+m]+=abs(py[i]-py[i+1]);break;}
                case 0:{val[j][i+m]+=-py[i]-py[i+1];break;}
            }
        }
    }
    F(i,1,m) F(j,1,9) q[0][j].emplace(val[0][i]+val[j][i],i);
    F(i,1,n) F(j,1,9) q[j][10].emplace(val[10][i+m]+val[j][i+m],i+m);
    F(i,1,n) ans+=abs(px[i]-px[i+1])+abs(py[i]-py[i+1]);
    F(k,1,n){
        F(i,0,10) F(j,0,10){
            while(!q[i][j].empty()&&!del[i][j].empty()&&q[i][j].top()==del[i][j].top()) q[i][j].pop(),del[i][j].pop();
            if(q[i][j].empty()) dis[i][j]=-INF;
            else dis[i][j]=q[i][j].top().fi;
        }
        memset(dep,-0x3f,sizeof(dep));
        static bool isin[11];
        queue<int>qu;
        qu.push(0);
        dep[0]=0,isin[0]=1;
        while(!qu.empty()){
            int now=qu.front();
            qu.pop();isin[now]=0;
            F(i,0,10) if(dep[i]<dep[now]+dis[now][i]){
                dep[i]=dep[now]+dis[now][i],fr[i]=now;
                if(!isin[i]) isin[i]=1,qu.push(i);
            }
        }
        ans+=dep[10];
        cout<<ans<<" ";
        int now=10,tp=0;
        static int u[11],v[11],mid[11];
        while(now){
            int i=fr[now],t=q[i][now].top().se;
            era(i,t,now);
            ++tp,u[tp]=i,mid[tp]=t,v[tp]=now;
            now=i;
        }
        R(i,tp,1) dir[u[i]][mid[i]]*=-1,dir[v[i]][mid[i]]*=-1,val[u[i]][mid[i]]*=-1,val[v[i]][mid[i]]*=-1;
        while(tp) add(u[tp],mid[tp],v[tp]),--tp;
    }
    return 0;
}