题意：有一个技能学习表，是一个DAG，要想正常学习到技能x，要将指向x的技能全部先学到，然后会有一个正常花费cx。然后你还有一种方案，通过氪金dx直接获得技能x。你还可以通过一定的代价，切断一条边。问你学得指定的技能N的最小代价。
源点向每个点连接代价为cx的边，每个点拆点，内部连接代价为dx的边，然后N向汇点连接代价为无穷的边，然后每条原图中的边的容量为切断其的代价。
容易发现，每一个割集的方案恰好对应一种学习到N的所需代价的方案。所以直接跑最小割即可。
#include#include #include #include using namespace std;typedef long long ll;#define INF 2147483647000ll#define MAXN 1005#define MAXM 32005ll cap[MAXM];int v[MAXM],en,first[MAXN],nex[MAXM];int d[MAXN],cur[MAXN];queue q;int S,T;void Init_Dinic(){memset(first,-1,sizeof(first)); en=0;}void AddEdge(const int &U,const int &V,const ll &W){ v[en]=V; cap[en]=W; nex[en]=first[U]; first[U]=en++; v[en]=U; cap[en]=0; nex[en]=first[V]; first[V]=en++;}bool bfs(){ memset(d,-1,sizeof(d)); q.push(S); d[S]=0; while(!q.empty()) { int U=q.front(); q.pop(); for(int i=first[U];i!=-1;i=nex[i]) if(d[v[i]]==-1 && cap[i]) { d[v[i]]=d[U]+1; q.push(v[i]); } } return d[T]!=-1;}ll dfs(int U,ll a){ if(U==T || !a) return a; ll Flow=0,f; for(int &i=cur[U];i!=-1;i=nex[i]) if(d[U]+1==d[v[i]] && (f=dfs(v[i],min(a,cap[i])))) { cap[i]-=f; cap[i^1]+=f; Flow+=f; a-=f; if(!a) break; } if(!Flow) d[U]=-1; return Flow;}ll max_flow(){ ll Flow=0,tmp=0; while(bfs()) { memcpy(cur,first,sizeof(first)); while(tmp=dfs(S,INF)) Flow+=tmp; } return Flow;}int n,m,nn;int main(){// freopen("d.in","r",stdin); int x,y,zu; ll z; scanf("%d",&zu); for(;zu;--zu){ Init_Dinic(); scanf("%d%d%d",&n,&m,&nn); S=n*2+1; T=S+1; for(int i=1;i<=m;++i){ scanf("%d%d%lld",&x,&y,&z); AddEdge(x+n,y,z); } for(int i=1;i<=n;++i){ scanf("%lld",&z); AddEdge(S,i,z); } for(int i=1;i<=n;++i){ scanf("%lld",&z); AddEdge(i,i+n,z); } AddEdge(nn+n,T,INF); printf("%lld\n",max_flow()); } return 0;}