BZOJ 3876 [Ahoi2014&Jsoi2014]支线剧情

题目大意

给你一个有向无环图，每次可以从1号点出发，到任意点结束，每条边有一个费用，求经过所有点至少一次的最少费用。

emmmmmm?????黑人问号.jpg

有上下界费用流是真的难= =

通用建图方法为：如有源汇，从可能的汇点向源点连边，容量INF，费用0；对于原图的边(x,y),下界l,上界r,连边$SS \to y$，容量为l,费用为这条边的费用；$x \to y$连边，容量为$r-l$，费用为原费用；对于每个点，连$x \to TT$，容量为下界的出度大小，费用为0.

之后$SS \to TT$的最小费用最大流就是答案。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1000
#define M 500000
#define INF (1<<30)
int n,S,T,dis[N],pre[N],frm[N],ans;
int to[M],nxt[M],val[M],cst[M],head[N],tot=1;
queue<int>q;
inline void AE(int x,int y,int a,int b)
{
	to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=a,cst[tot]=b;
	to[++tot]=x,nxt[tot]=head[y],head[y]=tot,val[tot]=0,cst[tot]=-b;
}
bool spfa()
{
	memset(dis,0x3f,sizeof dis),dis[S]=0;
	q.push(S);
	while(!q.empty())
	{
		int tmp=q.front();q.pop();
		for(int i=head[tmp];i;i=nxt[i])
			if(val[i]&&dis[to[i]]>dis[tmp]+cst[i])
			{
				dis[to[i]]=dis[tmp]+cst[i];
				frm[to[i]]=tmp,pre[to[i]]=i;
				q.push(to[i]);
			}
	}
	return dis[T]!=0x3f3f3f3f;
}
int main()
{
	scanf("%d",&n),S=0,T=n+1;
	int tmp,tx,ty;
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&tmp);
		AE(i,1,INF,0),AE(i,T,tmp,0);
		while(tmp--)
		{
			scanf("%d%d",&tx,&ty);
			AE(S,tx,1,ty),AE(i,tx,INF,ty);
		}
	}
	while(spfa())
	{
		tmp=INF;
		for(int i=T;i!=S;i=frm[i]) tmp=min(tmp,val[pre[i]]);
		ans+=tmp*dis[T];
		for(int i=T;i!=S;i=frm[i]) val[pre[i]]-=tmp,val[pre[i]^1]+=tmp;
	}
	printf("%d\n",ans);
	return 0;
}