Kejin Game

首先在15年这是一道金牌题(可能现在不是了)

难点在于,没有明确的提示是网络流,想到网络流不一定想到最小割,想到最小割还有会建模

当然这个建模没有那么鬼畜,主要是思路历程要想对。

---

$决策1:直接购买某个点,不需要任何依赖$

$决策2:对于某个无依赖的点,可以直接购买$

$决策3:对于某条依赖边,可以直接购买$

开始往费用流之类的方向想,都会遇到一个瓶颈

就是流无法解决多对一的关系(所有依赖边小时候才能执行决策2)

所以我们想到了最小割.

$我们的模型应该具有以下几个功能$

$考虑简单的一条链的依赖,s-1-2-3-4-5-t$

$假如我们对5使用决策1,那么s-t应该直接断掉(满足最小割)$

$假如我们对4使用决策1,那么[1,4]应该都不考虑,已经和t断开(一个割)$

$但是仍满足s-4-5-t的路线,因为后面还需要割开$

具体建模

$所以我们知道,一个点满足不了要求,把u点拆为u和u^{\prime }$

$对于原图的u-v边,从u^{\prime }向v^{\prime }连一条流量为边费用的边$

$u向u^{\prime }连一条流量为决策1的边$

$s向u连一条流量为决策2的边$

$跑最小割即可$

一些解释

$由于对于一个点u,要么买了所有前置依赖边,要么直接决策一购买这个点$

$由于u-u^{\prime }有决策1的边,割掉相当于选择,前面所有依赖边相当于都割掉了$

$又因为有s到u为决策2的边,如果割掉这条边,还需要割掉所有到u的依赖边才可以彻底割掉$

$这就满足了s到t的最小割就是我们的最小决策$

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; const int inf=1e9; int n,m,s,t,dis[maxn],in[maxn]; struct edge{ int to,nxt,flow; }d[maxn]; int head[maxn],cnt=1; void add(int u,int v,int flow){ d[++cnt]=(edge){v,head[u],flow},head[u]=cnt; d[++cnt]=(edge){u,head[v],0},head[v]=cnt; } bool bfs() { for(int i=0;i<=t;i++) dis[i]=0; dis[s]=1; queue<int>q; q.push( s ); while( !q.empty() ) { int u=q.front(); q.pop(); for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( d[i].flow&&dis[v]==0 ) { dis[v]=dis[u]+1; if( v==t ) return true; q.push( v ); } } } return false; } int dinic(int u,int flow) { if( u==t ) return flow; int res=flow; for(int i=head[u];i&&res;i=d[i].nxt ) { int v=d[i].to; if( dis[v]==dis[u]+1&&d[i].flow) { int temp=dinic(v,min(res,d[i].flow) ); if( temp==0 ) dis[v]=0; res-=temp; d[i].flow-=temp; d[i^1].flow+=temp; } } return flow-res; } signed main() { int T; cin >> T; while( T-- ) { int z; cin >> n >> m >> z; s=0,t=n*2+1; for(int i=1;i<=m;i++) { int l,r,w; cin >> l >> r >> w; add(l+n,r,w); } for(int i=1;i<=n;i++) { int x; cin >> x; add(s,i,x); } for(int i=1;i<=n;i++) { int x; cin >> x; add(i,i+n,x); } add(z+n,t,inf); int ans=0; while( bfs() ) ans+=dinic(s,inf); cout << ans << endl; cnt=1; for(int i=0;i<=t;i++) head[i]=0,in[i]=0; } }