专栏文章

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

PPurslaneM2GA
AT_abc224_h题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miq8l5e3
此快照首次捕获于
2025/12/04 00:43
3 个月前
此快照最后确认于
2025/12/04 00:43
3 个月前
查看原文

Solution

众所周知 CTT 之前不能考单纯性算法，但没说不能考线性规划的对偶。
容易发现每个数最多为 100100，所以显然可以拆点之后最小割建模，复杂度堪忧。
写成线性规划的形式：
给定变量 x1,2,⋯ ,Lx_{1,2,\cdots,L} 和 y1,2,⋯ ,Ry_{1,2,\cdots,R} 满足 xi,yi≥0x_i,y_i \ge 0，有限制 xui+yvi≥wix_{u_i} + y_{v_i} \ge w_i，最小化 ∑i=1LAixi+∑i=1RBiyi\sum_{i=1}^L A_ix_i + \sum_{i=1}^R B_iy_i。
显然要进行对偶。不是有 mm 条限制吗，我们给它写成这样：
minimizex,y≥0maximizeλ≥0∑i=1LAixi+∑i=1RBiyi+∑i=1m(wi−xui−yvi)λi\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
如果有 wi≥xui+yviw_i \ge x_{u_i} + y_{v_i}，就可以通过调整 λ\lambda 使得右边这个式子无穷大，自然不会最终有用。
通过对偶原则，把最大化和最小化颠倒顺序，得到：
maximizeλ≥0minimizex,y≥0∑i=1LAixi+∑i=1RBiyi+∑i=1m(wi−xui−yvi)λi\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 当做决策变量，xix_i、yiy_i 当做约束条件，即：
Ai≥∑e=(i,j)λeA_i \ge \sum_{e=(i,j)} \lambda_e
以及
Bi≥∑e=(j,i)λeB_i \ge \sum_{e=(j,i)} \lambda_e
并且最大化 ∑i=1mwiλi\sum_{i=1}^m w_i \lambda_i。
这个东西就是费用流模板了。
这是一个最大费用最大流，不好。但是注意到总的最大流是确定的（贪心保证），所以可以用一个极大的数 NN 减去边权，得到新的费用，转化为最小费用最大流问题。
如果你在费用流里面套一个原始对偶，可以做到 O(n3+n2Alog⁡n)O(n^3 + n^2 A \log n)。但是我懒。
这是代码：
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...