题目大意：给你一棵技能树，如果要学习一个技能，那么它之前的技能要全部学完，第 i 个点需要ai 能学习
每条边有一个消耗c 如果支付c那么就能去掉这条边， 你还可以kejin 花费di 就能直接学习 第 i 个技能，
问你最少花费多少能学习到s。
思路：这个最小割好难想啊， 将每个点拆成两个点 i 和 i + n，
1. 如果i 和 j 之间有边那么 i + n 向 j 建一条流量为边的消耗的边。
2. i 和 i + n 建一条流量为 di 的边
3. S 向 i 建一条流量为 ai 的边
4. s + n 向 T 建一条流量为 inf 的边
然后跑最大流得到最小割。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define piii pair<int, pair<int,int> > using namespace std; const int N = + ;
const int M = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; int n, m, s, tot, S, T, head[N << ], level[N << ]; struct node {
int u, v, w, nx;
} edge[M << ]; void add(int u, int v, int w) {
edge[tot].u = u; edge[tot].v = v; edge[tot].w = w;
edge[tot].nx = head[u]; head[u] = tot++;
} bool bfs() {
memset(level, , sizeof(level));
queue<int> que;
level[S] = ; que.push(S); while(!que.empty()) {
int u = que.front(); que.pop();
if(u == T) return true; for(int i = head[u]; ~i; i = edge[i].nx) { int v = edge[i].v;
if(level[v] || edge[i].w <= ) continue;
level[v] = level[u] + ;
que.push(v);
}
}
return false;
} int dfs(int u, int p) {
if(u == T) return p;
int ret = ;
for(int i = head[u]; ~i; i = edge[i].nx) {
int v = edge[i].v, w = edge[i].w;
if(level[v] != level[u] + || w <= ) continue;
int f = dfs(v, min(p - ret, w));
ret += f;
edge[i].w -= f;
edge[i ^ ].w += f;
if(ret == p) break;
}
if(!ret) level[u] = ;
return ret;
} int Dinic() {
int ans = ;
while(bfs()) ans += dfs(S, inf);
return ans;
} void init() {
tot = ;
memset(head, -, sizeof(head));
} int main() {
int cas; scanf("%d", &cas);
while(cas--) {
scanf("%d%d%d", &n, &m, &s);
S = , T = * n + ;
init(); for(int i = ; i <= m; i++) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
add(u + n, v, w); add(v, u + n, );
} for(int i = ; i <= n; i++) {
int x; scanf("%d", &x);
add(S, i, x); add(i, S, );
} for(int i = ; i <= n; i++) {
int x; scanf("%d", &x);
add(i, i + n, x);
add(i + n, i, );
} add(s + n, T, inf);
add(T, s + n, );
printf("%d\n", Dinic());
}
return ;
} /*
*/