自动搬运

查看原文

来自洛谷，原作者为

	绝顶我为峰 蓝的盆。

搬运于2025-08-24 22:17:00，当前版本为作者最后更新于2020-02-10 19:01:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

update1:感谢

update2:上次修改不完全，仍有残余错误。

给一个有向图，求用若干个环（或点）将整张图覆盖的最小花费。

求最小覆盖，想到带权二分图匹配问题，可以用费用流一波带走。

我们发现 $n\leq 500$ 其实很小，足够我们跑一遍 Floyd 求出覆盖两个点的最小花费。然后我们将每一个点拆成两个点 $(u,u')$ ，建立超级源超级汇 $s,t$ 进行如下建模：

• 从 $s$ 向 $u$ 连一条流量为 $1$，费用为 $0$ 的边；

• 从 $u'$ 向 $t$ 连一条流量为 $1$，费用为 $0$ 的边；

• 对于每一个点 $u$，从 $u$ 向 $u'$ 连一条流量为 $\inf$ ，费用为 $a_u$ 的边；

• 对于点对 $(u,v)$，如果从 $u$ 可以到达 $v$，就从 $u$ 向 $v'$ 连一条流量为 $1$，费用为 $dis_{i\rightarrow j}$ 的边。

我们发现这张图一定存在完美匹配，那么就跑一遍最小费用最大流就可以拿到 70pts。

为什么会超时呢？因为跑一遍 Floyd 会使 $m$ 达到 $O(n^2)$，显然无法承受。

我们考虑减少边的数量，由于最短路是由若干条路径拼成的，我们可以只在网络流建模中连接数据给出的边，同时从 $u'$ 向 $u$ 连一条流量为 $\inf$，费用为 $0$ 的边（这应该是标准套路了）。这样我们可以顺着这些边走出一条最短路径，而且边的数量减少到 $O(m+n)$，可以通过本题。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int unsigned long long
struct edge
{
	int nxt,to,weight,value;
}e[1000001<<1];
int n,m,tot=1,h[10005],dep[10005],cur[10005],s,t,a[5001],cost,ans,hg[10005];
bool vis[10005];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-')
			f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
inline void add(int x,int y,int w,int val)
{
	e[++tot].nxt=h[x];
	h[x]=tot;
	e[tot].to=y;
	e[tot].weight=w;
	e[tot].value=val;
}
inline bool Dijkstra()
{
	for(register int i=0;i<=t;++i)
	{
		vis[i]=0;
		dep[i]=0x3f3f3f3f;
		cur[i]=h[i];
	}
	__gnu_pbds::priority_queue<pair<int,int>,greater<pair<int,int> >,pairing_heap_tag> q;
	q.push(make_pair(0,t));
	dep[t]=0;
	while(!q.empty())
	{
		pair<int,int> k=q.top();
		q.pop();
		if(vis[k.second])
			continue;
		vis[k.second]=1;
		for(register int i=h[k.second];i;i=e[i].nxt)
			if(e[i^1].weight&&dep[e[i].to]>dep[k.second]-e[i].value+hg[k.second]-hg[e[i].to])
			{
				dep[e[i].to]=dep[k.second]-e[i].value+hg[k.second]-hg[e[i].to];
				q.push(make_pair(dep[e[i].to],e[i].to));
			}
	}
	return dep[0]!=dep[s];
}
int dfs(int k,int f)
{
	int r=0;
	if(!f||k==t)
	{
		vis[t]=1;
		ans+=f;
		return f;
	}
	int used=0;
	vis[k]=1;
	for(register int i=cur[k];i;i=e[i].nxt)
	{
		cur[k]=i;
		if((!vis[e[i].to]||e[i].to==t)&&dep[e[i].to]==dep[k]-e[i].value+hg[k]-hg[e[i].to]&&e[i].weight)
			if((r=dfs(e[i].to,min(f-used,e[i].weight))))
			{
				cost+=e[i].value*r;
				e[i].weight-=r;
				e[i^1].weight+=r;
				used+=r;
				if(f==used)
				{
					//vis[k]=0;
					break;
				}
			}
	}
	return used;
}
inline int dinic()
{
	while(Dijkstra())
	{
		vis[t]=1;
		while(vis[t])
		{
			memset(vis,0,sizeof(vis));
			dfs(s,1<<20);
		}
		memset(vis,0,sizeof(vis));
		for(register int i=0;i<=t;++i)
			hg[i]+=dep[i];
	}
	return cost;
}
signed main()
{
	n=read(),m=read();
	s=n<<1|1;
	t=s+1;
	for(register int i=1;i<=n;++i)
	{
		a[i]=read();
		add(s,i,1,0);
		add(i,s,0,0);
		add(i+n,t,1,0);
		add(t,i+n,0,0);
		add(i,i+n,1<<20,a[i]);
		add(i+n,i,0,-a[i]);
		add(i+n,i,1<<20,0);
		add(i,i+n,0,0);
	}
	for(register int i=1;i<=m;++i)
	{
		int x=read(),y=read(),w=read();
		add(x,y+n,1<<20,w);
		add(y+n,x,0,-w);
	}
	printf("%lld\n",dinic());
	return 0;
}