【BZOJ3876】[AHOI2014&JSOI2014] 支线剧情（无源汇有上下界网络流）

点此看题面

大致题意： 有一张\(DAG\)，经过每条边有一定时间，从\(1\)号点出发，随时可以返回\(1\)号点，求经过所有边的最短时间。

无源汇有上下界网络流

这是无源汇有上下界网络流的板子题。

可以先去看看这道题学习一下无源汇有上下界可行流的基本知识：【LOJ115】无源汇有上下界可行流。

我们对于题目中的每条边，在网络流图中连容量下界为\(1\)、容量上界为\(INF\)、代价为经过其时间的边。

对于除\(1\)号点外的每个点，在网络流图中将其向\(1\)连容量下界为\(0\)、上界为\(INF\)、代价为\(0\)的边。

然后，我们按照上面这题的套路处理一下建好网络流图。

接下来我们可以发现，这就是要求最小费用可行流。

那就把可行流中原本的最大流改成最小费用最大流即可。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 300

#define K 5000

#define INF 1e9

using namespace std;

int n;

template<int PS,int ES> class NetFlow//网络流

{

	private:

		#define add(x,y,f,c) (addE(x,y,f,c),addE(y,x,0,-c))

		#define addE(x,y,f,c) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].F=f,e[ee].C=c)

		#define El(x) ((((x)-1)^1)+1)

		int Ct,S,T,ee,p[PS+5],lnk[PS+5],lst[PS+5],F[PS+5],C[PS+5],Iq[PS+5];queue<int> q;

		struct edge {int to,nxt,F,C;}e[2*ES+5];

		I bool SPFA()//SPFA找增广路

		{

			RI i,k;for(i=1;i<=n+2;++i) F[i]=C[i]=INF;C[S]=0,q.push(S),Iq[S]=1;

			W(!q.empty())

			{

				for(Iq[k=q.front()]=0,q.pop(),i=lnk[k];i;i=e[i].nxt) e[i].F&&C[k]+e[i].C<C[e[i].to]&&

				(

					F[e[i].to]=min(F[k],e[i].F),C[e[i].to]=C[k]+e[i].C,lst[e[i].to]=i,

					!Iq[e[i].to]&&(q.push(e[i].to),Iq[e[i].to]=1)

				);

			}return F[T]!=INF;

		}

	public:

		I void Add(CI x,CI y,CI Mn,CI Mx,CI c) {add(x,y,Mx-Mn,c),p[x]-=Mn,p[y]+=Mn,Ct+=Mn*c;}//建边

		I void Solve()

		{

			RI x;S=n+1,T=n+2;for(RI i=1;i<=n;++i) p[i]>0&&add(S,i,p[i],0),p[i]<0&&add(i,T,-p[i],0);//建边使其满足流量平衡

			W(SPFA()) {Ct+=F[T]*C[T],x=T;W(x^S) e[lst[x]].F-=F[T],e[El(lst[x])].F+=F[T],x=e[El(lst[x])].to;}//跑最小费用最大流

			printf("%d",Ct);//输出答案

		}

};NetFlow<N+2,2*N+K> Fl;

int main()

{

	RI i,x,y,z;for(scanf("%d",&n),i=1;i<=n;++i)

		for(scanf("%d",&x);x;--x) scanf("%d%d",&y,&z),Fl.Add(i,y,1,INF,z);//对于边建边

	for(i=2;i<=n;++i) Fl.Add(i,1,0,INF,0);return Fl.Solve(),0;//对于点建边

}

巴特西

【BZOJ3876】[AHOI2014&JSOI2014] 支线剧情（无源汇有上下界网络流）

无源汇有上下界网络流

代码

最新文章

热门文章