自动搬运

查看原文

来自洛谷，原作者为

	w4p3r I think all our memories, and everything in it. . .can be nothing but the fiction we tell ourselves.

搬运于2025-08-24 21:46:04，当前版本为作者最后更新于2018-12-14 00:10:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言:

本来自己曾想到与这道题一模一样的模型的，我本来还准备自己出道这样的题的，结果被自己省的省选先出了，那就只能写篇题解了。。。

思路：

通过分析，我们可以得出，这道题实质所求的是：

在第i个点只能选$A[i]$次的情况下（$A[1],A[n]=inf$）,能选出多少条$1-n$的最短路

设$1$到第$i$个点的最短路径为$dist[i]$,第$i$个点和第$j$个点之间的边长为$e[i][j]$(没有的话当然就是$inf$了),那么显然的:

若我们要走$1$到$n$的最短路，我们只能走:$dist[v]=dist[u]+e[u][v]$的边

然后现在只剩下满足条件的边后，思路也很明显了，很显然这是一个最大流的问题，但是唯一讨厌的就是改题是对经过点的容量进行了限制，而不是对边。

那怎么办呢？

做过一些最大流的同学也都知道，现在当然就该拆点了。

拆完点，然后跑最大流就好了。

做法：

先跑最短路，留下在最短路中的边。

将$n$个点拆成$2n$个点，（其中$1$对应$1+n$,$2$对应$2+n$...）

从第$i(1<=i<=n)$个点向第$i+n$个点建一条容量为$A[i]$的边(为了每个点经过的流不超过A)

对于每条在最短路中的$e[u][v]$，从第$u+n$个点朝第$v$个点建一条容量为$inf$的边

从源点$s$朝点$1$建一条容量为$inf$的边,从点$2*n$朝汇点$t$建一条容量为$inf$的边

最后跑最大流即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#define inf 0x7fffffffff/2
#define eps 1e-6
#define N 2010
#define M 100010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
	char ch=getchar();
	ll s=0,w=1;
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return s*w;
}
ll dist[N];//这道题最坑的就是没开long long 0分,rip for 2015年参加省选没开long long的学长们
struct edge
{
	int next,to;
	ll fl;
}e[M<<1];
int cnt=1,head[N];
int n,m;
int vis[N];
ll c[N];
int s,t;
int depth[N];
queue<int>Q;
vector<int>to[N];
vector<ll>v[N];
inline void add_edge(int from,int to,ll fl)
{
	e[++cnt].to=to;
	e[cnt].next=head[from];
	e[cnt].fl=fl;
	head[from]=cnt;
}//建边
inline int bfs()
{
	while(!Q.empty())Q.pop();memset(depth,0,sizeof(depth));
	Q.push(s);depth[s]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(register int i=head[x];i;i=e[i].next)
		{
			if(!depth[e[i].to]&&e[i].fl>0)
			{
				depth[e[i].to]=depth[x]+1;
				Q.push(e[i].to);
			}
		}
	}
	return depth[t];
}
ll dfs(int now,ll flow)
{
	if(now==t)return flow;
	ll ret=0;
	for(register int i=head[now];i;i=e[i].next)
	{
		if(ret==flow)return ret;
		if(depth[e[i].to]==depth[now]+1&&e[i].fl>0)
		{
			ll fl=dfs(e[i].to,min(flow-ret,e[i].fl));
			if(fl>0)
			{
				ret+=fl;
				e[i].fl-=fl;
				e[i^1].fl+=fl;
			}
		}
	}
	return ret;
}
inline ll Dinic()
{
	ll sum=0;
	while(bfs())
	{
		ll x=1;while(x){x=dfs(s,inf);sum+=x;}
	}
	return sum;
}//最大流
inline void spfa()
{
	for(register int i=2;i<=n;i++)dist[i]=inf;
	while(!Q.empty())Q.pop();
	Q.push(1);vis[1]=1;
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();vis[x]=0;
		for(register int i=0;i<to[x].size();i++)
		{
			int go=to[x][i];
			ll val=v[x][i];
			if(dist[x]+val<dist[go])
			{
				dist[go]=dist[x]+val;
				if(!vis[go])
				{
					vis[go]=1;
					Q.push(go);
				}
			}
		}
	}
}//最短路，Dijkstra过不了· 
int main()
{
	n=read(),m=read();
	t=n*2+1;
	for(register int i=1;i<=m;i++)
	{
		int x=read(),y=read();
		ll val=read();
		to[x].push_back(y);v[x].push_back(val);
		to[y].push_back(x);v[y].push_back(val);
	}
	spfa();
	for(register int i=1;i<=n;i++)c[i]=read();
	add_edge(s,1,inf);add_edge(1,s,0);
	add_edge(2*n,t,inf);add_edge(t,2*n,0);
	for(register int i=1;i<=n;i++)
	{
		if(i!=1&&i!=n){add_edge(i,i+n,c[i]);add_edge(i+n,i,0);}
		else {add_edge(i,i+n,inf),add_edge(i+n,i,0);}
	}//通过拆点对每个点经过的流量进行限制
	for(register int i=1;i<=n;i++)
	{
		for(register int j=0;j<to[i].size();j++)
		{
			int go=to[i][j];
			ll val=v[i][j];
			if(dist[go]==dist[i]+val)//在最短路中
			{
				add_edge(i+n,go,inf);add_edge(go,i+n,0);
			}
		}
	}//对在最短路中的边建边 
	printf("%lld\n",Dinic());
	return 0;
}

后记：

这道题与网络流24题中的最长不下降序列问题类似，都是对DP方案数的讨论（最短路我认为也是一种DP），做完这道题没做那道题的经验可以去A一下（双倍经验）

如果认为我这篇题解对你有帮助的可以给我点一下赞qwq。如果有任何疑问，或者认为我的题解有什么问题的话，请务必私信我，感激不尽！我会努力把我的题解写得最好的!