牛客练习赛52 发传单(上下界最小费用最小流)

F.发传单

题意

$wjyyy$可以给一部分人发传单,有传递代价

拿到传单的人可以发给另一些人,有传递代价

要求满足花费最少的传单,且传递代价最小

假如是个$DAG$图我们可以做最小路径覆盖

但这里不是,所以想到上下界网络最小流(暂时不考虑费用)

解出来后,重新建图设置每条边的流量不超过求出的最小流,跑费用流即可

但是这样代码太长了而且很难调

$有种简单的方法$

直接跑上下界最小费用流

但是我们把$wjyyy$传递出的传单费用$+inf$

这样最小费用流就会尽量少的选择,最小流

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=4e5+10; const int inf=1e9; int a[maxn]; int n,m,vis[maxn],s,t,ss,tt,in[maxn],dis[maxn],pre[maxn],flow[maxn]; struct edge{ int to,nxt,flow,w; }d[maxn]; int head[maxn],cnt=1,ans; void add(int u,int v,int flow,int w) { d[++cnt]=(edge){v,head[u],flow,w},head[u]=cnt; d[++cnt]=(edge){u,head[v],0,-w},head[v]=cnt; } void ins(int u,int v,int l,int r,int w) { add(u,v,r-l,w); in[u]-=l,in[v]+=l,ans+=l*w; } bool spfa(int s,int t) { for(int i=0;i<=tt;i++) dis[i]=1e18; queue<int>q; q.push(s); dis[s]=0, flow[s]=inf; while( !q.empty() ) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( dis[v]>dis[u]+d[i].w&&d[i].flow ) { dis[v] = dis[u]+d[i].w; pre[v]=i; flow[v]=min( flow[u],d[i].flow ); if( !vis[v] ) vis[v]=1,q.push(v); } } } return (dis[t]!=1e18); } int dinic(int s,int t) { int ans=0,x,i; while( spfa(s,t) ) { ans+=flow[t]*dis[t]; x=t; while( x!=s ) { i = pre[x]; d[i].flow-=flow[t],d[i^1].flow+=flow[t]; x = d[i^1].to; } } return ans; } signed main() { cin >> n; s=0,t=n+n+1; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) { ins(s,i,0,inf,a[i]+inf); ins(i+n,t,0,inf,0); ins(i,i+n,1,inf,0); int k; cin >> k; while( k-- ) { int v,w; cin >> v >> w; ins(i+n,v,0,inf,w); } } ss=t+1,tt=ss+1; for(int i=s;i<=t;i++) { if( in[i]>0 ) add(ss,i,in[i],0); else add(i,tt,-in[i],0); } add(t,s,inf,0); cout << ( ans+dinic(ss,tt) )%inf; }