BZOJ 2502 清理雪道

题目大意

给你一张有向无环图，每次你从任意一个点出发，求遍历所有边至少一次的最少出发次数。

有上下界的最小流问题。

此类问题解决方法如下：正常建图，边权为$r-l$。记录每个点的度du[i]，表示到它的流量下界和减去从它发出的流量下界和。如果$du[i] \gt 0$那么连边$SS \to i$，边权$du[i]$；如果$du[i] \gt 0$那么连边$i \to TT$，边权$-du[i]$。连边$T \to S$，边权INF。进行$SS \to TT$的最大流，记录$T \to S$的边流了多少，加到ans上。之后撤掉$T \to S$的边，撤掉$SS,TT$相连的所有边，跑一次$T \to S$的最大流，用ans减去即为答案。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 110
#define M 500000
#define INF (1<<30)
int n,du[N],S,T,SS,TT,depth[N];
int to[M],nxt[M],val[M],head[N],tot=1;
queue<int>q;
inline void AE(int x,int y,int z)
{
	to[++tot]=y,nxt[tot]=head[x],head[x]=tot,val[tot]=z;
	to[++tot]=x,nxt[tot]=head[y],head[y]=tot,val[tot]=0;
}
inline void mkpath(int pos)
{
	int cnt,tmp;
	scanf("%d",&cnt);
	if(!cnt) AE(pos,T,INF);
	for(int i=1;i<=cnt;++i)
	{
		scanf("%d",&tmp);
		du[pos]--,du[tmp]++,AE(pos,tmp,INF-1);
	}
}
bool BFS(int x,int y)
{
	while(!q.empty()) q.pop();
	q.push(x);
	memset(depth,-1,sizeof depth),depth[x]=0;
	while(!q.empty())
	{
		int tmp=q.front();q.pop();
		for(int i=head[tmp];i;i=nxt[i])
			if(val[i]&&depth[to[i]]==-1)
			{
				depth[to[i]]=depth[tmp]+1;
				if(to[i]==y) return true;
				q.push(to[i]);
			}
	}
	return false;
}
int dinic(int pos,int tgt,int left)
{
	if(pos==tgt) return left;
	int nleft=left;
	for(int i=head[pos];i;i=nxt[i])
		if(val[i]&&depth[to[i]]==depth[pos]+1)
		{
			int tmp=dinic(to[i],tgt,min(nleft,val[i]));
			if(!tmp) depth[to[i]]=-1;
			nleft-=tmp,val[i]-=tmp,val[i^1]+=tmp;
			if(!nleft) break;
		}
	return left-nleft;
}
int main()
{
	scanf("%d",&n),S=0,T=n+1,SS=n+2,TT=n+3;
	for(int i=1;i<=n;++i) AE(S,i,INF),mkpath(i);
	for(int i=0;i<=n+1;++i)
	{
		if(du[i]>0) AE(SS,i,du[i]);
		if(du[i]<0) AE(i,TT,-du[i]);
	}
	AE(T,S,INF);
	int ans=0;
	while(BFS(SS,TT)) ans+=dinic(SS,TT,INF);
	ans=val[tot],val[tot]=val[tot-1]=0;
	for(int i=head[SS];i;i=nxt[i]) val[i]=val[i^1]=0;
	for(int i=head[TT];i;i=nxt[i]) val[i]=val[i^1]=0;
	while(BFS(T,S)) ans-=dinic(T,S,INF);
	printf("%d\n",ans);
	return 0;
}