[AHOI2014/JSOI2014]支线剧情（luogu）
看到“花费最少时间”等字眼可以想到建一个费用流的图
我们对于每一个剧情 i 可以通过 花费时间 t 的支线剧情 到剧情 b 的关系建一条从 i 到 b ，费用为 t 的边
然而这些边流量上界为 INF ，下界为 1
我们再从每个不为 1 的 i 向 1 连一条费用为0，流量上界为INF，下界为 0 的边
于是我们得到一张无源汇，且流量有上下界的网络流图
首先每条边下界必须流满，于是记ans为 每条边费用*流量下界 的和，再将每条边改造成下界为 0 ，上界为 原上界-原下界
而下界为 0 =无下界，所以可以开始求最小费用最大流了吗
源汇点都没有怎么求最大流！！我一定是在口胡读者
这都是小事，最大的问题是，这时求最小费用最大流可能会导致每个点真实入流！=真实出流
为了解决这个问题，我们建立源点 s ，汇点 t，
设 d[i] =点 i 在改造前的 入边流量下界和-出边流量下界和
对于每个 i ，若d[i]>0 , 从 s 向 i 连一条费用为 0 ，流量为 d[i] 的边
若d[i]<0 , 从 i 向 t 连一条费用为 0 ，流量为 -d[i] 的边
于是此时求最小费用最大流，最小费用+ans即为答案
Code
#include <cstdio> #include <cstdlib> #include <algorithm> #include <queue> #include <cstring> using namespace std; const int N=500,M=2e5; int head[N],ver[M],nxt[M],cost[M],edge[M],tot=1; int n,k,a,b,s,t,d[N],sum,mc,mf,dis[N],incf[N],pre[N],inf=1<<30; bool in[N]; void add(int u,int v,int w,int c) { ver[++tot]=v,nxt[tot]=head[u],edge[tot]=w,cost[tot]=c,head[u]=tot; ver[++tot]=u,nxt[tot]=head[v],edge[tot]=0,cost[tot]=-c,head[v]=tot; } bool spfa() { memset(dis,0x3f,sizeof(dis)); pre[t]=-1,pre[s]=0,dis[s]=0,incf[s]=inf; queue <int> q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); in[u]=false; for(int i=head[u],v;i;i=nxt[i]) if(edge[i]>0 && dis[v=ver[i]]>dis[u]+cost[i]) { dis[v]=dis[u]+cost[i]; pre[v]=i,incf[v]=min(edge[i],incf[u]); if(!in[v]) in[v]=true,q.push(v); } } return pre[t]!=-1; } void update() { mc+=incf[t]*dis[t],mf+=incf[t]; int x=t; while(x!=s) { int i=pre[x]; edge[i]-=incf[t],edge[i^1]+=incf[t]; x=ver[i^1]; } } int main() { scanf("%d",&n); s=0,t=n+1; for(int i=1;i<=n;i++) { scanf("%d",&k); while(k--) { scanf("%d%d",&a,&b); add(i,a,inf,b); sum+=b; d[i]--,d[a]++; } } for(int i=2;i<=n;i++) add(i,1,inf,0); for(int i=1;i<=n;i++) if(d[i]>0) add(s,i,d[i],0); else if(d[i]<0) add(i,t,-d[i],0); while(spfa()) update(); printf("%d",sum+mc); return 0; }
[AHOI2014/JSOI2014]支线剧情（最小费用可行流）
原文：https://www.cnblogs.com/hsez-cyx/p/12484523.html