门

题目

每条边至少走一次，起点为1的有向无环图，最少走的权值最小

题解

。。。明显就是源点为1的下界为1上界INF的费用流
但上下界咋做来着

---

有源汇需要汇向源连(INF，0)的边变成无源汇
要假设全都到了下界，然后将剩余流量改为$up_i-low_i$
然后看这样流进的和流出的大小关系，$in>out$就连$S->i$,反之连$i->T$
最后跑遍普通网络流即可

#include<bits/stdc++.h>
using namespace std;
const int N=3e4+10,M=5e4+10,INF=0x3F3F3F3F;
int n,s,t,S,T;
int head[N],nex[M],to[M],fl[M],val[M],tot=1;
void build(int u,int v,int f,int w)
{
	tot++;nex[tot]=head[u];to[tot]=v;val[tot]=w;fl[tot]=f;head[u]=tot;
	tot++;nex[tot]=head[v];to[tot]=u;val[tot]=-w;fl[tot]=0;head[v]=tot;
}
int dis[N],flw[N],pre[N];
bool vis[N];
bool spfa()
{
	memset(pre,0,sizeof(pre));
	memset(vis,0,sizeof(vis));
	memset(flw,0x7f/3,sizeof(flw));
	memset(dis,0x3F,sizeof(dis));
	queue<int>q;q.push(S);
	dis[S]=0;vis[S]=1;
	while(!q.empty())
	{
		int u=q.front();q.pop();vis[u]=0;
		for(int i=head[u];i;i=nex[i])
		{
			int v=to[i];
			if(fl[i]&&dis[v]>dis[u]+val[i])
			{
				flw[v]=min(fl[i],flw[u]);
				dis[v]=dis[u]+val[i];
				pre[v]=i;
				if(!vis[v])vis[v]=1,q.push(v);
			}
		}
	}return dis[T]<0x3F3F3F3F;
}
int maxflow,mincost;	
void water()
{
	while(spfa())
	{
		int fw=flw[T];
		maxflow+=fw;mincost+=dis[T]*fw;
		int now=T;
		while(now!=S)
		{
			int x=pre[now];
			fl[x]-=fw;fl[x^1]+=fw;
			now=to[x^1];
		}
	}
}
int d[N];
int main()
{
	scanf("%d",&n);
	s=1,t=n+1,S=0,T=n+2;
	build(t,s,INF,0);
	for(int m,v,w,i=1;i<=n;i++)
	{
		scanf("%d",&m);
		while(m--)
		{
			scanf("%d%d",&v,&w);
			build(i,v,INF,w);
			mincost+=w;
			d[i]--,d[v]++;
		}build(i,t,INF,0);
	}
	for(int i=1;i<=n;i++)
	if(d[i]>0)	   build(S,i,d[i],0);
	else if(d[i]<0)build(i,T,-d[i],0);
	water();
	printf("%d",mincost);
}