模拟费用流学习笔记
就是用各种东西维护费用流，有退流的可以理解为反悔贪心，否则直接贪心。
来点典题
uoj445 UER#8 B
先让每个送餐员匹配左边的最优的餐厅，这个过程可以用堆维护餐厅的 (w-y) 的最小值。
匹配右边的情况考虑反悔，让右边的餐厅匹配送餐员，再开个堆维护 (-v-x)，(v)为这个送餐员的最优匹配。然后找到餐厅之后就在这个堆里找一个匹配，这个也要反悔，在餐厅的堆里加入 (-v+(w-y))
还有用后面的餐厅匹配前面已经匹配的送餐员的情况，在送餐员的堆中加入(-w-y) 。
还有用后面的送餐员匹配前面已经匹配的餐厅的情况，这种一定不会更优。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(ll i=a;i<=b;++i)
ll read(){
ll x=0,pos=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return pos?x:-x;
}
const ll N = 2e5+200;
ll ans;
ll n,m;
ll x[N],y[N],w[N],c[N];
struct node{
ll w;ll cnt;
node(ll w=0,ll cnt=0):w(w),cnt(cnt){}
};
struct cmp{
ll operator()(node a,node b){
return a.w>b.w;
}
};
priority_queue<node,vector<node>,cmp> q1,q2;
ll inf = 2e12;
void work1(ll now){
ll res=inf;
if(!q1.empty()){
node fr=q1.top();q1.pop();
res=fr.w+x[now];
if((--fr.cnt)>0) q1.push(fr);
}
ans+=res;
q2.push(node(-res-x[now],1));
}
void work2(ll now){
ll rc=c[now];
while(!q2.empty()&&rc>0){
ll nw=q2.top().w+w[now]+y[now];
if(nw>=0) break;
if(rc<=q2.top().cnt){
ans+=nw*rc;
q1.push(node(-nw+w[now]-y[now],rc));
node fr=q2.top();fr.cnt-=rc;rc=0;q2.pop();if(fr.cnt!=0) q2.push(fr);
break;
}else{
rc-=q2.top().cnt;
ans+=nw*q2.top().cnt;
q1.push(node(-nw+w[now]-y[now],q2.top().cnt));
q2.pop();
}
}
if(c[now]>rc){
q2.push(node(-w[now]-y[now],c[now]-rc));
}
if(rc){
q1.push(node(w[now]-y[now],rc));
}
}
int main(){
n=read(),m=read();
FOR(i,1,n) x[i]=read();
ll tot=0;
FOR(i,1,m){
y[i]=read(),w[i]=read(),c[i]=read();tot+=c[i];
}
if(tot<n){
printf("-1");
return 0;
}
for(ll i=1,j=1;i<=n||j<=m;){
if(i<=n&&(j>m||x[i]<y[j])){
work1(i++);
}else work2(j++);
}
printf("%lld
",ans);
return 0;
}
loj6405. 「ICPC World Finals 2018」征服世界
在LCA合并，添加反悔。可以发现不会同时反悔，所以写起来很方便。
注意一个都不匹配是最优的，而题目要求是所有军队都匹配，所以先把每个匹配的权值减去 (inf) 就能让匹配数优先级大于权值。最后还要加上 (sum y_i*inf) 。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,a,b) for(ll i=a;i<=b;++i)
ll read(){
ll x=0,pos=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') pos=0;
for(;isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
return pos?x:-x;
}
const ll N = 2.5e5+200;
ll n,m;
ll x[N],y[N],w[N],c[N];
struct node{
mutable ll w;ll cnt;
node(ll w=0,ll cnt=0):w(w),cnt(cnt){}
int operator <(node b){
return w<b.w;
}
}val[N*30];
int son[N*30],nex[N*30],num=0;
struct heap{
int merge(int u,int v){
if(!u||!v) return u+v;
if(val[v]<val[u]) swap(u,v);nex[v]=son[u];son[u]=v;return u;
}
int merges(int u){
if(!u) return 0;if(!nex[u]) return u;
int v1=nex[u],v2=nex[v1];
nex[u]=nex[v1]=0;return merge(merge(u,v1),merges(v2));
}
int rt;
void pop(){rt=merges(son[rt]);}
void join(int x){rt=merge(rt,x);}
node &top(){return val[rt];}
void push(node now){val[++num]=now;rt=merge(rt,num);}
int empty(){return rt==0;}
}H[N*2],M[N*2];
#define pii pair<int,int>
#define fi first
#define se second
vector<pii>G[N];
const ll inf = 1e12;
ll ans=0;
void dfs(int now,int pre,ll dep){
H[now].push(node(dep,x[now]));
M[now].push(node(dep-inf,y[now]));
FOR(i,0,(int)G[now].size()-1){
int v=G[now][i].fi;if(v==pre) continue;
dfs(v,now,dep+G[now][i].se);
H[now].join(H[v].rt);
M[now].join(M[v].rt);
}
while(!H[now].empty()&&!M[now].empty()){
node &a=H[now].top(),&b=M[now].top();
ll nw=a.w+b.w-2*dep;
int cnt=min(a.cnt,b.cnt);
if(nw>=0) break;
ans+=nw*cnt;
a.cnt-=cnt,b.cnt-=cnt;if(!a.cnt) H[now].pop();if(!b.cnt) M[now].pop();
H[now].push(node(-nw+a.w,cnt));
M[now].push(node(-nw+b.w,cnt));
}
}
int main(){
n=read();
FOR(i,1,n-1){
int u=read(),v=read(),c=read();
G[u].push_back(make_pair(v,c));
G[v].push_back(make_pair(u,c));
}
ll sum=0;
FOR(i,1,n){
x[i]=read(),y[i]=read();sum+=y[i];
}
dfs(1,0,0);
printf("%lld
",ans+sum*inf);
return 0;
}
NOI2017 蔬菜
首先有个特别考思维的题意转化费用流，然后贪心地用堆维护就行了，甚至不需要反悔。最后还有一个思维点，没有退流，可以转化成递推。