BZOJ 3876 [Ahoi2014&Jsoi2014]支线剧情

题解：

带下界的费用流

对于x->y边权为z Addedge(x,t,1,0) Addedge(s,y,1,z) Addedge(x,y,inf,0)

然后对每个点Addedge(i,1,inf,0)

然后跑最小费用最大流即可

因为这是DAG，所以每一个循环流都是从1到某个点再到1的路径

也就是说用几个费用最小的循环流来满足下界

#include<iostream>

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

using namespace std;

const int maxn=3000;

const int oo=1000000000;

int n;

struct Edge{

	int from,to,cap,flow,cost;

};

vector<int>G[maxn];

vector<Edge>edges;

void Addedge(int x,int y,int z,int w){

	Edge e;

	e.from=x;e.to=y;e.cap=z;e.flow=0;e.cost=w;

	edges.push_back(e);

	e.from=y;e.to=x;e.cap=0;e.flow=0;e.cost=-w;

	edges.push_back(e);

	int c=edges.size();

	G[x].push_back(c-2);

	G[y].push_back(c-1);

}

int s,t,totn;

int inq[maxn];

int d[maxn];

int pre[maxn];

queue<int>q;

int Spfa(int &nowflow,int &nowcost){

	for(int i=1;i<=totn;++i){

		inq[i]=0;d[i]=oo;

	}

	d[s]=0;inq[s]=1;q.push(s);

	while(!q.empty()){

		int x=q.front();q.pop();inq[x]=0;

		for(int i=0;i<G[x].size();++i){

			Edge e=edges[G[x][i]];

			if((e.cap>e.flow)&&(d[x]+e.cost<d[e.to])){

				d[e.to]=d[x]+e.cost;

				pre[e.to]=G[x][i];

				if(!inq[e.to]){

					inq[e.to]=1;

					q.push(e.to);

				}

			}

		}

	}

	if(d[t]==oo)return 0;

	int x=t,f=oo;

	while(x!=s){

		Edge e=edges[pre[x]];

		f=min(f,e.cap-e.flow);

		x=e.from;

	}

	nowflow+=f;nowcost+=f*d[t];

	x=t;

	while(x!=s){

		edges[pre[x]].flow+=f;

		edges[pre[x]^1].flow-=f;

		x=edges[pre[x]].from;

	}

	return 1;

}

int Mincost(){

	int flow=0,cost=0;

	while(Spfa(flow,cost)){

	}

	return cost;

}

int main(){

	scanf("%d",&n);

	s=n+1;t=n+2;totn=t;

	for(int i=1;i<=n;++i){

		int m;scanf("%d",&m);

		Addedge(i,t,m,0);

		while(m--){

			int y,z;

			scanf("%d%d",&y,&z);

//			Addedge(i,y,oo,z);

			Addedge(s,y,1,z);

		}

	}

	for(int i=2;i<=n;++i)Addedge(i,1,oo,0);

	printf("%d\n",Mincost());

	return 0;

}