CODE

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int MAXP = 1510;

const int MAXN = 505;

const int MAXM = 5005;

const int INF = 0x3f3f3f3f;

int n, a[MAXN], rt[2], q[2], fa[2][MAXN], lim[2][MAXN];

vector<int>G[2][MAXN];

int S, T, ans;

void dfs(int o, int u) {

	int siz = G[o][u].size(), v;

	for(int i = 0; i < siz; ++i)

		if((v=G[o][u][i]) != fa[o][u]) {

			fa[o][v] = u;

			dfs(o, v);

		}

}

int info[MAXP], fir[MAXP], to[MAXM], nxt[MAXM], c[MAXM], w[MAXM], cnt=1;

inline void link(int u, int v, int cc, int ww) {

	to[++cnt] = v, nxt[cnt] = fir[u], fir[u] = cnt; c[cnt] = cc, w[cnt] = ww;

	to[++cnt] = u, nxt[cnt] = fir[v], fir[v] = cnt; c[cnt] = 0, w[cnt] = -ww;

}

int dis[MAXP];

bool inq[MAXP];

inline bool spfa() {

	static queue<int> q;

	memset(dis, -1, sizeof dis);

	dis[S] = 0; q.push(S);

	while(!q.empty()) {

		int u = q.front(); q.pop(); inq[u] = 0;

		for(int i = fir[u], v; i; i = nxt[i])

			if(c[i] && dis[v=to[i]] < dis[u] + w[i]) {

				dis[v] = dis[u] + w[i];

				if(!inq[v]) inq[v] = 1, q.push(v);

			}

	}

	return ~dis[T];

}

bool vis[MAXP];

int Aug(int u, int Max) {

	if(u == T) { ans += Max * dis[T]; return Max; }

	vis[u] = 1;

	int delta, flow = 0;

	for(int &i = info[u], v; i; i = nxt[i])

		if(c[i] && dis[v=to[i]] == dis[u] + w[i] && !vis[v] && (delta=Aug(v, min(Max-flow, c[i])))) {

			flow += delta, c[i] -= delta, c[i^1] += delta;

			if(flow == Max) break;

		}

	vis[u] = 0; return flow;

}

inline void Max_Cost_flow() {

	while(spfa())

		memcpy(info, fir, sizeof fir), Aug(S, INF);

}

int main () {

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i)

		scanf("%d", &a[i]);

	for(int o = 0; o < 2; ++o) {

		scanf("%d", &rt[o]);

		for(int i = 1, x, y; i < n; ++i)

			scanf("%d%d", &x, &y), G[o][x].pb(y), G[o][y].pb(x);

		dfs(o, rt[o]);

	}

	memset(lim, 0x3f, sizeof lim);

	for(int o = 0; o < 2; ++o) {

		scanf("%d", &q[o]);

		for(int i = 1, x, y; i <= q[o]; ++i)

			scanf("%d%d", &x, &y), lim[o][x] = y;

	}

	S = 0, T = 3*n + 1;

	for(int i = 1; i <= n; ++i) {

		link(fa[0][i], i, lim[0][i], 0);

		link(fa[1][i]?n+fa[1][i]:0, n+i, lim[1][i], 0);

		link(i, 2*n+i, 1, 0);

		link(n+i, 2*n+i, 1, 0);

		link(2*n+i, T, 1, a[i]);

	}

	Max_Cost_flow();

	printf("%d\n", ans);

}
巴特西

ZrOJ #878. 小K与赞助 (网络流)

CODE

最新文章

热门文章
