题目链接请戳
解题思路
用最大流。需要注意的只有拆点
代码
#include#include #include #include #define N 300#define INF 1e9using namespace std;int cap[N][N], flow[N][N], a[N], pre[N];int n, m, b, d;queue q;int EK(int s, int t){ memset(flow, 0, sizeof(flow)); int f = 0; for (;;) { memset(a, 0, sizeof(a)); a[s] = INF; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 1; v <= t; v++) if (!a[v] && flow[u][v] < cap[u][v]) { pre[v] = u; q.push(v); a[v] = min(a[u], cap[u][v] - flow[u][v]); } } if (a[t] == 0) break; for (int u = t; u != s; u = pre[u]) { flow[pre[u]][u] += a[t]; flow[u][pre[u]] -= a[t]; } f += a[t]; } return f;} int main(){ while (scanf("%d", &n) != EOF) { memset(cap, 0, sizeof(cap)); for (int i = 1; i <= n; i++) { int v; scanf("%d", &v); cap[i][i+n] = v; } scanf("%d", &m); for (int i = 0; i < m; i++) { int x, y, v; scanf("%d%d%d", &x, &y, &v); cap[x+n][y] = v; } scanf("%d%d", &b, &d); for (int i = 0; i < b; i++) { int x; scanf("%d", &x); cap[0][x] = INF; } for (int i = 0; i < d; i++) { int x; scanf("%d", &x); cap[x+n][2*n+1] = INF; } printf("%d\n", EK(0, 2*n+1)); } return 0;}