线性规划对偶入门 & 题解：AT_abc224_h [ABC224H] Security Camera 2

· · 题解

Solution

众所周知 CTT 之前不能考单纯性算法，但没说不能考线性规划的对偶。

容易发现每个数最多为 100，所以显然可以拆点之后最小割建模，复杂度堪忧。

写成线性规划的形式：

给定变量 x_{1,2,\cdots,L} 和 y_{1,2,\cdots,R} 满足 x_i,y_i \ge 0，有限制 x_{u_i} + y_{v_i} \ge w_i，最小化 \sum_{i=1}^L A_ix_i + \sum_{i=1}^R B_iy_i。

显然要进行对偶。不是有 m 条限制吗，我们给它写成这样：

\text{minimize}_{x,y \ge 0} \text{maximize}_{\lambda \ge 0} \sum_{i=1}^L A_ix_i + \sum_{i=1}^R B_iy_i + \sum_{i=1}^m (w_i - x_{u_i} - y_{v_i})\lambda_i

如果有 w_i \ge x_{u_i} + y_{v_i}，就可以通过调整 \lambda 使得右边这个式子无穷大，自然不会最终有用。

通过对偶原则，把最大化和最小化颠倒顺序，得到：

\text{maximize}_{\lambda \ge 0} \text{minimize}_{x,y \ge 0} \sum_{i=1}^L A_ix_i + \sum_{i=1}^R B_iy_i + \sum_{i=1}^m (w_i - x_{u_i} - y_{v_i})\lambda_i

这时候把 \lambda 当做决策变量，x_i、y_i 当做约束条件，即：

A_i \ge \sum_{e=(i,j)} \lambda_e

以及

B_i \ge \sum_{e=(j,i)} \lambda_e

并且最大化 \sum_{i=1}^m w_i \lambda_i。

这个东西就是费用流模板了。

这是一个最大费用最大流，不好。但是注意到总的最大流是确定的（贪心保证），所以可以用一个极大的数 N 减去边权，得到新的费用，转化为最小费用最大流问题。

如果你在费用流里面套一个原始对偶，可以做到 O(n^3 + n^2 A \log n)。但是我懒。

这是代码：

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXV=200+10,MAXE=100000+10;
int lim,ll,rr,m,s,t,mc,mf,tmp,tot=1,ev,deg[MAXV],hd[MAXV],cur[MAXV],dis[MAXV],vis[MAXV];
struct Edge {int to,nxt,f,c;}edge[MAXE];
void add_edge(int u,int v,int f,int c) {return edge[++tot]={v,hd[u],f,c},hd[u]=tot,edge[++tot]={u,hd[v],0,-c},hd[v]=tot,void();}
int spfa(int s,int t) {
    ffor(i,s,t) dis[i]=0x3f3f3f3f,vis[i]=0,cur[i]=hd[i];
    queue<int> q;
    dis[s]=0,q.push(s);
    while(!q.empty()) {
        int u=q.front();
        vis[u]=0,q.pop();
        for(int i=hd[u];i;i=edge[i].nxt) {
            int to=edge[i].to,f=edge[i].f,c=edge[i].c;
            if(!f||dis[to]<=dis[u]+c) continue ;
            dis[to]=dis[u]+c;
            if(!vis[to]) vis[to]=1,q.push(to);
        }
    }
    return dis[t]!=0x3f3f3f3f;
}
int dinic(int u,int mx,int s,int t) {
    if(u==t) return mx;
    int res=0;
    vis[u]=1;
    for(int i=cur[u];i;i=edge[i].nxt) {
        int to=edge[i].to,f=edge[i].f,c=edge[i].c; cur[u]=i;
        if(dis[to]!=dis[u]+c||vis[to]||!f) continue ;
        int tmp=dinic(to,min(mx,f),s,t);
        if(tmp) {
            res+=tmp,mx-=tmp,mc+=c*tmp,edge[i].f-=tmp,edge[i^1].f+=tmp;
            if(!mx) break;
        }
        else dis[to]=0x3f3f3f3f;
    }
    return vis[u]=0,res;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>ll>>rr;
    s=0,t=ll+rr+1;
    ffor(i,1,ll) cin>>lim,add_edge(s,i,lim,0);
    ffor(i,1,rr) cin>>lim,add_edge(i+ll,t,lim,0);
    ffor(i,1,ll) ffor(j,1,rr) cin>>lim,add_edge(i,j+ll,10000000,100-lim);
    while(spfa(s,t)) while(lim=dinic(s,10000000,s,t)) mf+=lim;
    cout<<100*mf-mc;
    return 0;
}