题解：P17199 [KOI 2026 #2] 工厂

· · 题解

题意简述

每名员工在所属日期的白天，以及相邻的两个夜间工作。 每个时段都按熟练度排序，将相邻两人配成一组。 需要选择若干员工，使所有时段人数为偶数， 并最大化生产利润减去基本工资与夜间补贴。

解题思路

把应聘者按熟练度从小到大排序并依次扫描。 对每个日期 d，定义二进制变量 p_d， 表示当前前缀中属于第 d 天且被雇用的员工人数奇偶性。

扫描开始前有 p_d=0。 扫描结束后也必须有 p_d=0， 这正好保证每个白天都有偶数名员工。 第 d 天夜间的员工来自日期 d 与 d+1， 所以两个白天人数均为偶数时，所有夜间人数也必为偶数。

先把目标改成最小化：

\text{总工资}-\text{生产利润}

考虑所属日期为 d 的一名应聘者。 处理前后的奇偶性分别记为 x,y。 不雇用时 x=y，雇用时 x\ne y， 所以基本工资产生代价 C|x-y|。

若发生 0\to1，这名员工是当天某一组中熟练度较低的人， 其生产利润贡献为 -B，目标函数增加 B。 若发生 1\to0，他是熟练度较高的人， 生产利润贡献为 B，目标函数减少 B。 两种情况可以统一写成：

C|x-y|+B(y-x)

下面把夜间补贴拆到相邻熟练度之间的间隙。 定义边界状态 p_0=p_{T+1}=0。 第 d 天夜间由日期 d 和 d+1 的员工组成， 扫描完一个前缀后，该夜已选人数的奇偶性为：

p_d\mathbin{\operatorname{xor}}p_{d+1}=|p_d-p_{d+1}|

设当前与下一名应聘者的熟练度差为 w。 某个夜间的一组员工会跨过这个间隙， 当且仅当间隙左侧已有奇数名该夜员工。 因此，这个间隙对全部夜间补贴的贡献为：

w\sum_{d=0}^{T}|p_d-p_{d+1}|

这是因为一组员工的熟练度差， 恰好等于两个端点之间所有相邻熟练度差之和。 逐个间隙统计，便会准确还原每一组的补贴。

如果为每个前缀与每天都建立变量，点数会达到 O(NT)。 实际上，p_d 只会在扫描到属于日期 d 的应聘者时改变。 因此，每名应聘者只需建立一个节点， 表示处理完他以后所属日期的新奇偶性。

维护 now[d]，表示日期 d 当前使用的状态节点。 处理第 i 名应聘者时，旧节点为 now[D_i]，新节点为 i。 在两者之间加入员工代价，再令 now[D_i]=i。 每个熟练度间隙出现时， 使用当前各天节点加入全部相邻日期的绝对值代价。

所有代价都是二进制变量的一次项或绝对值项，可以转成最小割。 代码规定源点侧表示变量值 1，汇点侧表示变量值 0。 固定为 0 的初始状态直接使用汇点表示。

对于 w|x-y|，在两个节点之间加入容量为 w 的无向边。 只有两个变量不同，这条边才会被割开，割边代价正好为 w。

对于一次项 kx：

员工代价中的 B(y-x)， 分别给旧节点增加系数 -B，给新节点增加系数 B。 最后，将每天的最终状态节点与汇点用无穷容量无向边相连， 强制所有最终奇偶性为 0。

求出最大流后，从源点沿正剩余容量搜索即可得到最小割两侧。 一名员工的旧、新状态节点分处两侧， 当且仅当该天奇偶性发生翻转，也就是这名员工被雇用。

任意合法雇用方案都会唯一确定扫描过程中的全部状态。 员工项准确给出其基本工资与白天利润， 间隙项准确给出全部夜间补贴， 所以对应割的代价等于该方案的总工资减去生产利润。

反过来，无穷容量边保证每天最终状态为 0。 任意有限割都能按状态是否翻转恢复出合法雇用方案， 并且恢复出的方案与割具有相同代价。 因此，最小割的相反数就是题目要求的最大值，恢复出的员工集合也是最优方案。

建立所有间隙项需要 O(NT) 时间。 某一天的状态更新后，只有它左右相邻的状态对发生变化， 所以合并平行边后只有 O(N) 种绝对值项。 容量矩阵负责合并这些边，图中有 O(N) 个点和 O(N) 条边。 Dinic 算法的时间复杂度为 O(N^3)，总空间复杂度为 O(N^2)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=505;
const ll inf=0x3f3f3f3f3f3f3f3f;
struct person
{
    int a,b,c,d,id;
}p[N];
struct edge
{
    int v,r;
    ll w;
};
struct flow
{
    vector<edge> g[N];
    int d[N],cur[N];
    void add(int u,int v,ll w,ll r=0)
    {
        int x=g[u].size();
        int y=g[v].size();
        g[u].push_back({v,y,w});
        g[v].push_back({u,x,r});
    }
    bool bfs(int s,int t)
    {
        memset(d,-1,sizeof d);
        queue<int> q;
        d[s]=0;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(const edge &e:g[u])
                if(e.w&&d[e.v]==-1)
                {
                    d[e.v]=d[u]+1;
                    q.push(e.v);
                }
        }
        return d[t]!=-1;
    }
    ll dfs(int u,int t,ll lim)
    {
        if(u==t)return lim;
        ll res=0;
        int siz=g[u].size();
        for(int &i=cur[u];i<siz&&lim;i++)
        {
            edge &e=g[u][i];
            if(!e.w||d[e.v]!=d[u]+1)continue;
            ll w=dfs(e.v,t,min(lim,e.w));
            if(!w)continue;
            e.w-=w;
            g[e.v][e.r].w+=w;
            lim-=w;
            res+=w;
        }
        return res;
    }
    ll dinic(int s,int t)
    {
        ll res=0;
        while(bfs(s,t))
        {
            memset(cur,0,sizeof cur);
            ll w;
            while((w=dfs(s,t,inf)))res+=w;
        }
        return res;
    }
    void find(int s,bool vis[])
    {
        memset(vis,0,sizeof(bool)*N);
        queue<int> q;
        vis[s]=1;
        q.push(s);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(const edge &e:g[u])
                if(e.w&&!vis[e.v])
                {
                    vis[e.v]=1;
                    q.push(e.v);
                }
        }
    }
}f;
int now[N],pre[N];
ll coef[N],cost[N][N];
bool vis[N];
void add(int x,int y,ll w)
{
    if(x==y||w==0)return;
    if(x>y)swap(x,y);
    cost[x][y]+=w;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        cin>>p[i].a>>p[i].b>>p[i].c>>p[i].d;
        p[i].id=i+1;
    }
    sort(p,p+n,[](const person &x,const person &y)
    {
        return x.a<y.a;
    });
    int s=n;
    int t=n+1;
    fill(now,now+m+1,t);
    for(int i=0;i<n;i++)
    {
        int x=now[p[i].d];
        pre[i]=x;
        add(x,i,p[i].c);
        if(x!=t)coef[x]-=p[i].b;
        coef[i]+=p[i].b;
        now[p[i].d]=i;
        if(i==n-1)continue;
        ll w=p[i+1].a-p[i].a;
        add(t,now[1],w);
        for(int j=1;j<m;j++)add(now[j],now[j+1],w);
        add(t,now[m],w);
    }
    for(int i=1;i<=m;i++)add(t,now[i],inf);
    for(int i=0;i<=t;i++)
        for(int j=i+1;j<=t;j++)
            if(cost[i][j])f.add(i,j,cost[i][j],cost[i][j]);
    ll val=0;
    for(int i=0;i<n;i++)
        if(coef[i]>=0)f.add(i,t,coef[i]);
        else
        {
            val+=coef[i];
            f.add(s,i,-coef[i]);
        }
    val+=f.dinic(s,t);
    f.find(s,vis);
    vector<int> ans;
    for(int i=0;i<n;i++)
        if(vis[i]!=vis[pre[i]])ans.push_back(p[i].id);
    int siz=ans.size();
    cout<<-val<<'\n';
    cout<<siz<<'\n';
    for(int i=0;i<siz;i++)
    {
        if(i)cout<<' ';
        cout<<ans[i];
    }
    cout<<'\n';
    return 0;
}