2023.2.1 日寄
一言
缺乏温暖的人极力渴望温暖，恰似飞蛾扑火，最终，焚身以火
%你赛
复习内容：模拟费用流
「NEERC2016」 Mole Tunnels
题解
\(~~~~\) 动态加边肯定没办法每次跑网络流。那怎么做呢？
\(~~~~\) 模拟费用流，预处理出每个点子树内最近的食物点，那么 \(u\) 这个点会从初始位置往上到某个点然后钻进子树里的食物点。我们把这个过程模拟费用流做了即可。
\(~~~~\) 因为是二叉树，所以树高 \(\log n\) ，暴力跳完全没问题。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
#define ls u<<1
#define rs u<<1|1
int n,m;
const int INF=1e9;
int f[400005],g[100005];
int c[100005],pos[100005],Flow[100005];
void Update(int u)
{
f[u]=INF;
if(c[u]) f[u]=0,g[u]=u;
if(ls<=n&&f[ls]+(Flow[ls]<0?-1:1)<f[u]) f[u]=f[ls]+(Flow[ls]<0?-1:1),g[u]=g[ls];
if(rs<=n&&f[rs]+(Flow[rs]<0?-1:1)<f[u]) f[u]=f[rs]+(Flow[rs]<0?-1:1),g[u]=g[rs];
}
#undef ls
#undef rs
int main() {
read(n);read(m);
for(int i=1;i<=n;i++) read(c[i]);
for(int i=1;i<=m;i++) read(pos[i]);
memset(f,127,sizeof(f));
for(int i=n;i>=1;i--) Update(i);//更新i点最近的食物点
// for(int i=1;i<=n;i++) cerr<<f[i]<<" "<<g[i]<<endl;
ll Ans=0;
for(int i=1;i<=m;i++)
{
int Minn=INF,P=0,u=pos[i],Up=0,Anc=0;
while(u)
{
// cerr<<u<<endl;
if(Minn>f[u]+Up) Minn=f[u]+Up,P=g[u],Anc=u;
Up+=(Flow[u]>0?-1:1); u>>=1;
}
u=pos[i]; Ans+=Minn;
// cerr<<Minn<<" "<<P<<" "<<u<<" "<<Up<<" "<<Anc<<endl;
while(u!=Anc) Flow[u]--,Update(u>>1),u>>=1;
c[P]--; Update(P);
while(P!=Anc) Flow[P]++,Update(P>>1),P>>=1;
while(Anc) Update(Anc),Anc>>=1;
printf("%lld ",Ans);
}
return 0;
}
讲下面部分题目之前先来点模型。
一些模拟费用流的模型
\(~~~~\) 数轴上有 \(n\) 只老鼠，\(m\) 个老鼠洞，每只老鼠到老鼠洞的代价等于其距离。每个老鼠洞只能容纳 \(1\) 只老鼠。
\(\sf{Type 1}\)
\(~~~~\) 每只老鼠只能向左走，求最小代价。
\(~~~~\) 直接把所有的老鼠和洞拉通排序，然后每只老鼠找到上一个洞即可。
\(\sf{Type 2}\)
\(~~~~\) 老鼠可以向左向右走，求最小代价。
\(~~~~\) 开两个堆，依然都只匹配往左的，不同的是洞也可以往左匹配没有匹配上的老鼠。两边交叉反悔。
\(~~~~\) 放一个其他博主的代码。
priority_queue<int>q0,q1;
//q0维护未匹配的老鼠，q1维护未匹配的洞
for(int i=1;i<=n;i++)
{
if(op[i]==1)//洞
{
if(q0.top()+a[i]<0)//洞去让前面的老鼠反悔更优
{
Ans+=q0.top()+a[i];
q1.push(-q0.top()-a[i]*2);//前面的老鼠反悔选到这个地方的洞
q0.pop();
}
else q1.push(-a[i]);//这个洞等待匹配
}
else //鼠
{
Ans+=q1.top()+a[i];//匹配前面的洞
q0.push(-q1.top()-a[i]*2);//反悔这个老鼠
q1.pop();
}
}
\(\sf{Type 3}\)
\(~~~~\) 进洞也有代价 \(w_j\)。
\(~~~~\) 把 \(w_j\) 加入上面的 \(w_j\) 部分就好了。
\(\sf{Type 4}\)
\(~~~~\) 每个洞可以容纳 \(b_i\) 只老鼠。
\(~~~~\) 把 \(b_i\) 加入堆的第二维，然后如果 \(b_i\) 还没空那就重新再放一个回去。
\(~~~~\) 当然上面的东西还可以组合。把各自部分重组就好了。
「BZOJ4977 Lydsy1708月赛」跳伞求生
题解
\(~~~~\) 把我方玩家的 \(a_i\) 视作坐标，敌方玩家的 \(b_i\) 也视作坐标，附带上一个 \(w_i\) 的额外权值。那就是只往左走的情况。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
struct node{
int Type,val,pri;
node(){}
node(ll T,ll V,ll P){Type=T,val=V,pri=P;}
}P[200005];
struct cmpQ{
bool operator()(const ll a,const ll b){return a<b;}
};
priority_queue<ll,vector<ll>,cmpQ>Q;
bool cmp(node a,node b){return a.pri==b.pri?a.Type<b.Type:a.pri<b.pri;}
int main() {
ll n,m;read(n);read(m);
for(ll i=1,a;i<=n;i++) read(a),P[i]=node(1,a,a);
for(ll i=1,b,c;i<=m;i++) read(b),read(c),P[n+i]=node(2,c-b,b);
sort(P+1,P+n+m+1,cmp);
ll Ans=0;
for(ll i=1;i<=n+m;i++)
{
if(P[i].Type==1)
{
if(Q.empty()) continue;
Ans+=Q.top()+P[i].val;Q.pop();
Q.push(-P[i].val);
}
else Q.push(P[i].val);
}
printf("%lld",Ans);
return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。
模拟费用流你别来找我，我怕反悔贪心误会。
*/
「UOJ 455」雪灾与外卖
题解
\(~~~~\) 左右都可以走，洞有容量有权值，把这三个结合一下就好了。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<ll,ll>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
struct cmpQ{
bool operator()(const PII a,const PII b){return a.first>b.first;}
};
priority_queue<PII,vector<PII>,cmpQ>Q0,Q1;//Q0:表示待匹配的鼠 Q1:表示待匹配的洞
struct node{
ll Type,x,Lim,Val;
}P[200005];
bool cmp(node a,node b){return a.x<b.x;}
int main() {
ll n,m;
read(n);read(m);
for(ll i=1;i<=n;i++) read(P[i].x),P[i].Type=1;
ll All=0,Ans=0;
for(ll i=n+1;i<=n+m;i++) read(P[i].x),read(P[i].Val),read(P[i].Lim),P[i].Type=2,All+=P[i].Lim;
if(All<n) return puts("-1")&0;
//为了防止最开始的鼠鼠和最后面的洞会被弃掉所以加上两个东西
P[n+m+1].Type=2; P[n+m+1].Lim=n; P[n+m+1].x=-1e18;
P[n+m+2].Type=2; P[n+m+2].Lim=n; P[n+m+2].x=1e18;
sort(P+1,P+1+n+m+2,cmp);
for(ll i=1;i<=n+m+2;i++)
{
if(P[i].Type==1)//鼠鼠
{
PII p=Q1.top();Q1.pop();
Ans+=p.first+P[i].x;
Q0.push(mp(-p.first-(P[i].x<<1),1));//反悔去匹配其他洞
if(p.second>1) p.second--,Q1.push(p);
}
else//洞
{
ll Times=P[i].Lim;
while(Times&&!Q0.empty()&&P[i].x+Q0.top().first+P[i].Val<0)
{
PII p=Q0.top();Q0.pop();
ll Now=min(Times,p.second);
Ans+=1ll*Now*(p.first+P[i].x+P[i].Val);
Q1.push(mp(-p.first-(P[i].x<<1),Now));//反悔去匹配其他鼠鼠
Times-=Now; p.second-=Now;
if(p.second) Q0.push(p);
}
if(P[i].Lim!=Times) Q0.push(mp(-P[i].x-P[i].Val,P[i].Lim-Times));//弃掉已选的
if(Times) Q1.push(mp(-P[i].x+P[i].Val,Times));
}
}
printf("%lld",Ans);
return 0;
}
/*
西风吹老洞庭波，一夜湘君白发多。
醉后不知天在水，满船清梦压星河。
*/