题解：
https://blog.csdn.net/litble/article/details/88410435
https://www.mina.moe/archives/11762
以下是我瞎bb的：
如果我没看错的话，这个模拟费用流模拟的根本不是一般的最短增广路算法，模拟的是消圈算法...无语，为什么网上好像都直接当成对的了。另外，如果真的从费用流模型开始思考的话，好像会累死人而且完全没有结果；还是应该当做一个贪心来看待，费用流当做证明方法就行了
消圈算法就是先随便跑一个最大流，然后每次找出任意一个"残量网络(指只保留'原图中边和用于退流的反向边中剩余可用容量不为0的边'形成的图)中的负费用环"，增广满，直到找不到负费用环，此时就是最小费用最大流（证明咕咕咕了）
这题里面如果遇到传送点时箱子堆是空的，就直接丢进传送点堆就行（代价自然为费用-位置）；如果遇到箱子时传送点堆是空的，要假设左侧无限远处有无限个传送点（由于传送点不一定必须被匹配，但是箱子一定必须被匹配）；同样的，遇到传送点时如果进行匹配不能让答案更小，就不要匹配，直接丢进传送点堆
这题餐厅可能可以多次匹配，方法是记一个pair，第二维是剩余容量，要拆的时候拆；直接这样搞复杂度是错的，但是向餐厅堆里面插入元素的次数是可以控制的（把多次一样的插入并成插入一次一个pair），这样复杂度就对了；复杂度证明网上有
最终代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
struct P
{
ll x,y;
};
bool operator<(const P &a,const P &b)
{
return a.x>b.x;
}
struct PP
{
int x,w,c;
}p[];
bool operator<(const PP &a,const PP &b)
{
return a.x<b.x;
}
int n,m;
ll ans;
priority_queue<P> q1,q2;
int main()
{
int i;P t;ll v,ts=,t1,t2;
scanf("%d%d",&n,&m);
for(i=;i<=n;++i)
{
scanf("%d",&p[i].x);
p[i].c=-;
}
for(i=;i<=m;++i)
{
scanf("%d%d%d",&p[i+n].x,&p[i+n].w,&p[i+n].c);
ts+=p[i+n].c;
}
if(n>ts) {puts("-1");return ;}
sort(p+,p+n+m+);
for(i=;i<=n+m;++i)
{
if(p[i].c==-)
{
if(q2.empty()) v=1e11;
else
{
t=q2.top();q2.pop();
v=t.x;
if(t.y!=) q2.push((P){t.x,t.y-});
}
ans+=p[i].x+v;
q1.push((P){-*p[i].x-v,});
}
else
{
t1=;
while(p[i].c && !q1.empty())
{
t=q1.top();v=t.x;
if(p[i].x+p[i].w+v>=) break;
q1.pop();
t2=min(ll(p[i].c),t.y);
t.y-=t2;p[i].c-=t2;
ans+=t2*(p[i].x+p[i].w+v);
t1+=t2;
q2.push((P){-*p[i].x-v,t2});
if(t.y) q1.push(t);
}
if(t1) q1.push((P){-p[i].x-p[i].w,t1});
if(p[i].c) q2.push((P){p[i].w-p[i].x,p[i].c});
}
}
printf("%lld\n",ans);
return ;
}
暴力（ 最暴力的费用流，$O(n^2)$条边）：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
struct pli
{
ll fi;int se;
};
bool operator>(const pli &a,const pli &b)
{
return a.fi>b.fi || (a.fi==b.fi && a.se>b.se);
}
const ll inf=0x3f3f3f3f3f3f3f3f;
namespace F
{ struct E
{
int to,nxt,from;
ll d,cap,flow;
}e[];
int f1[],ne=;
int S,T,n;
bool inq[],*vis=inq;
ll d[];
ll h[];
ll flow,cost;
typedef __gnu_pbds::priority_queue<pli,greater<pli> > pq;
pq::point_iterator it[];
//const int INF=0x3f3f3f3f;
bool spfa()
{
int u,k,k1;
memset(d,0x3f,sizeof(d[])*(n+));
memset(inq,,sizeof(inq[])*(n+));
queue<int> q;
q.push(T);d[T]=;inq[T]=;
while(!q.empty())
{
u=q.front();q.pop();
inq[u]=;
for(k1=f1[u];k1;k1=e[k1].nxt)
{
k=k1^;
if(e[k].cap>e[k].flow&&d[u]+e[k].d<d[e[k].from])
{
d[e[k].from]=d[u]+e[k].d;
if(!inq[e[k].from])
{
inq[e[k].from]=;
q.push(e[k].from);
}
}
}
}
return d[S]!=inf;
}
bool dij()
{
int i,u,k,k1;pli t;
memset(d,0x3f,sizeof(d[])*(n+));
memset(vis,,sizeof(vis[])*(n+));
pq q;
for(i=;i<=n;i++) it[i]=q.end();
it[T]=q.push((pli){,T});d[T]=;
while(!q.empty())
{
t=q.top();q.pop();
u=t.se;
if(vis[u]) continue;
vis[u]=;
for(k1=f1[u];k1;k1=e[k1].nxt)
{
k=k1^;
if(e[k].cap>e[k].flow&&d[u]+e[k].d+h[u]-h[e[k].from]<d[e[k].from])
{
d[e[k].from]=d[u]+e[k].d+h[u]-h[e[k].from];
if(it[e[k].from]!=q.end()) q.modify(it[e[k].from],(pli){d[e[k].from],e[k].from});
else it[e[k].from]=q.push((pli){d[e[k].from],e[k].from});
}
}
}
return d[S]!=inf;
}
void update()
{
for(int i=;i<=n;i++) h[i]+=d[i];
}
ll dfs(int u,ll x)
{
if(u==T||x==) return x;
ll flow=,f;
vis[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].cap>e[k].flow&&h[e[k].to]==h[u]-e[k].d)
{
f=dfs(e[k].to,min(x-flow,e[k].cap-e[k].flow));
e[k].flow+=f;e[k^].flow-=f;flow+=f;
if(flow==x) return flow;
}
return flow;
}
void augment()
{
ll f;
while()
{
memset(vis,,sizeof(vis[])*(n+));
f=dfs(S,inf);
if(!f) break;
flow+=f;cost+=f*h[S];
}
}
void solve()
{
flow=cost=;
memset(h,,sizeof(h[])*(n+));
if(!spfa()) return;
do
{
update();
augment();
}while(dij());
}
void me(int a,int b,ll c,ll d)
{
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;e[ne].from=a;
e[ne].cap=c;e[ne].d=d;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;e[ne].from=b;
e[ne].cap=;e[ne].d=-d;
} } ll abs1(ll a){return a>=?a:-a;}
int n,m;
int x[],y[],w[],c[];
int main()
{
int i,j;ll ts=;
scanf("%d%d",&n,&m);
for(i=;i<=n;++i)
scanf("%d",x+i);
for(i=;i<=m;++i)
{
scanf("%d%d%d",y+i,w+i,c+i);
ts+=c[i];
}
if(n>ts) {puts("-1");return ;}
F::S=n+m+;F::T=n+m+;F::n=n+m+;
for(i=;i<=n;++i)
F::me(F::S,i,,);
for(i=;i<=n;++i)
for(j=;j<=m;++j)
F::me(i,j+n,inf,abs1(x[i]-y[j]));
for(i=;i<=m;++i)
F::me(i+n,F::T,c[i],w[i]);
F::solve();
printf("%lld\n",F::cost);
return ;
}
暴力（优化到O(n)条边）：
%:pragma GCC optimize("Ofast")
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
struct pli
{
ll fi;int se;
};
bool operator>(const pli &a,const pli &b)
{
return a.fi>b.fi || (a.fi==b.fi && a.se>b.se);
}
const ll inf=0x3f3f3f3f3f3f3f3f;
namespace F
{
struct E
{
int to,nxt,from;
ll d,cap,flow;
}e[];
int f1[],ne=;
int S,T,n;
bool inq[],*vis=inq;
ll d[];
ll h[];
ll flow,cost;
typedef __gnu_pbds::priority_queue<pli,greater<pli> > pq;
pq::point_iterator it[];
//const int INF=0x3f3f3f3f;
bool spfa()
{
int u,k,k1;
memset(d,0x3f,sizeof(d[])*(n+));
memset(inq,,sizeof(inq[])*(n+));
queue<int> q;
q.push(T);d[T]=;inq[T]=;
while(!q.empty())
{
u=q.front();q.pop();
inq[u]=;
for(k1=f1[u];k1;k1=e[k1].nxt)
{
k=k1^;
if(e[k].cap>e[k].flow&&d[u]+e[k].d<d[e[k].from])
{
d[e[k].from]=d[u]+e[k].d;
if(!inq[e[k].from])
{
inq[e[k].from]=;
q.push(e[k].from);
}
}
}
}
return d[S]!=inf;
}
bool dij()
{
int i,u,k,k1;pli t;
memset(d,0x3f,sizeof(d[])*(n+));
memset(vis,,sizeof(vis[])*(n+));
pq q;
for(i=;i<=n;i++) it[i]=q.end();
it[T]=q.push((pli){,T});d[T]=;
while(!q.empty())
{
t=q.top();q.pop();
u=t.se;
if(vis[u]) continue;
vis[u]=;
for(k1=f1[u];k1;k1=e[k1].nxt)
{
k=k1^;
if(e[k].cap>e[k].flow&&d[u]+e[k].d+h[u]-h[e[k].from]<d[e[k].from])
{
d[e[k].from]=d[u]+e[k].d+h[u]-h[e[k].from];
if(it[e[k].from]!=q.end()) q.modify(it[e[k].from],(pli){d[e[k].from],e[k].from});
else it[e[k].from]=q.push((pli){d[e[k].from],e[k].from});
}
}
}
return d[S]!=inf;
}
void update()
{
for(int i=;i<=n;i++) h[i]+=d[i];
}
ll dfs(int u,ll x)
{
if(u==T||x==) return x;
ll flow=,f;
vis[u]=;
for(int k=f1[u];k;k=e[k].nxt)
if(!vis[e[k].to]&&e[k].cap>e[k].flow&&h[e[k].to]==h[u]-e[k].d)
{
f=dfs(e[k].to,min(x-flow,e[k].cap-e[k].flow));
e[k].flow+=f;e[k^].flow-=f;flow+=f;
if(flow==x) return flow;
}
return flow;
}
void augment()
{
ll f;
while()
{
memset(vis,,sizeof(vis[])*(n+));
f=dfs(S,inf);
if(!f) break;
flow+=f;cost+=f*h[S];
}
}
void solve()
{
flow=cost=;
memset(h,,sizeof(h[])*(n+));
if(!spfa()) return;
do
{
update();
augment();
}while(dij());
}
void me(int a,int b,ll c,ll d)
{
e[++ne].to=b;e[ne].nxt=f1[a];f1[a]=ne;e[ne].from=a;
e[ne].cap=c;e[ne].d=d;
e[++ne].to=a;e[ne].nxt=f1[b];f1[b]=ne;e[ne].from=b;
e[ne].cap=;e[ne].d=-d;
//printf("1t%d %d %lld %lld\n",a,b,c,d);
}
}
ll abs1(ll a){return a>=?a:-a;}
int n,m;
int x[],y[],w[],c[];
int main()
{
int i,j;ll ts=;
scanf("%d%d",&n,&m);
for(i=;i<=n;++i)
scanf("%d",x+i);
for(i=;i<=m;++i)
{
scanf("%d%d%d",y+i,w+i,c+i);
ts+=c[i];
}
if(n>ts) {puts("-1");return ;}
F::S=n+*m+;F::T=n+*m+;F::n=n+*m+;
for(i=;i<m;++i)
F::me(i,i+,inf,y[i+]-y[i]);
for(i=m;i>;--i)
F::me(i+m,i-+m,inf,y[i]-y[i-]);
for(i=;i<=m;++i)
{
F::me(i,i+*m,inf,);
F::me(i+m,i+*m,inf,);
F::me(i+*m,F::T,c[i],w[i]);
}
for(i=,j=;i<=n;++i)
{
while(j<=m && y[j]<x[i]) ++j;
if(j!=) F::me(i+*m,j-+m,,x[i]-y[j-]);
if(j!=m+) F::me(i+*m,j,,y[j]-x[i]);
F::me(F::S,i+*m,,);
}
F::solve();
printf("%lld\n",F::cost);
return ;
}
数据生成器
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<chrono>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
ull splitmix64(ull x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> )) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> )) * 0x94d049bb133111eb;
return x ^ (x >> );
}
ull rd()
{
static ull x=splitmix64(chrono::steady_clock::now().time_since_epoch().count());
return splitmix64(x=x*6364136223846793005ull+1442695040888963407ull);
}
ll randint(ll l,ll r)
{
return rd()%(r-l+)+l;
}
int n=randint(,),m=randint(,);
struct P
{
int y,w,c;
}t2[];
bool operator<(const P &a,const P &b)
{
return a.y<b.y;
}
int t1[];
int main()
{
int i;
for(i=;i<=n;++i)
t1[i]=randint(,1e9);
for(i=;i<=m;++i)
t2[i].y=randint(,1e9),t2[i].w=randint(,1e9),t2[i].c=randint(,1e9);
sort(t1+,t1+n+);
sort(t2+,t2+m+);
printf("%d %d\n",n,m);
for(i=;i<=n;++i)
printf("%d ",t1[i]);
puts("");
for(i=;i<=m;++i)
printf("%d %d %d\n",t2[i].y,t2[i].w,t2[i].c);
return ;
}
对拍脚本
#!/bin/bash
set -v on
while [ = ]
do
./1_2.out >t1.txt
echo "running 1"
./.out <t1.txt >t2.txt
echo "running 2"
./1_1.out <t1.txt >t3.txt
diff -w t2.txt t3.txt
if [ $? != ]
then read -n
fi
cat t2.txt
done
优化暴力和最终代码拍了一下，应该是没问题了
一堆草稿...
令