HDU - 3879 Base Station （最大权闭合子图）

A famous mobile communication company is planning to build a new set of base stations. According to the previous investigation, n places are chosen as the possible new locations to build those new stations. However, the condition of each position varies much, so the costs to built a station at different places are different. The cost to build a new station at the ith place is P i (1<=i<=n). 

When complete building, two places which both have stations can communicate with each other. 

Besides, according to the marketing department, the company has received m requirements. The ith requirement is represented by three integers A i, B i and C i, which means if place A i and B i can communicate with each other, the company will get C i profit. 

Now, the company wants to maximize the profits, so maybe just part of the possible locations will be chosen to build new stations. The boss wants to know the maximum profits.

Input

Multiple test cases (no more than 20), for each test case: 
The first line has two integers n (0<n<=5000) and m (0<m<=50000). 
The second line has n integers, P1 through Pn, describes the cost of each location. 
Next m line, each line contains three integers, A i, B i and C i, describes the ith requirement.

Output

One integer each case, the maximum profit of the company.

Sample Input

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

Sample Output

4

       将n个点和m个计划共同作为n+m个点，建超级源点和m个计划相连（边权为奖励），m个计划分别和他们的两个点相连（边权为inf），将n个点和超级源点相连（边权

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 100010;
const int maxm = 1000100;
struct *** {
	int v, w, ne;
}ed[maxm];
int n, m, cnt;
int head[maxn], dis[maxn], cur[maxn];
void init() {
	cnt = 0;
	memset(head, -1, sizeof(head));
}
void add(int u, int v, int w) {
	ed[cnt].v = v; ed[cnt].w = w;
	ed[cnt].ne = head[u]; head[u] = cnt++;
	ed[cnt].v = u, ed[cnt].w = 0;
	ed[cnt].ne = head[v]; head[v] = cnt++;
}
int bfs(int st, int en) {
	queue<int>q;
	memset(dis, 0, sizeof(dis));
	dis[st] = 1;
	q.push(st);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (u == en)return 1;
		for (int s = head[u]; ~s; s = ed[s].ne) {
			int v = ed[s].v;
			if (dis[v] == 0 && ed[s].w > 0) {
				dis[v] = dis[u] + 1; q.push(v);
			}
		}
	}
	return dis[en] != 0;
}
int dfs(int st, int en, int flow) {
	int ret = flow, a;
	if (st == en || flow == 0)return flow;
	for (int &s = cur[st]; ~s; s = ed[s].ne) {
		int v = ed[s].v;
		if (dis[v] == dis[st] + 1 && (a = dfs(v, en, min(ret, ed[s].w)))) {
			ed[s].w -= a;
			ed[s ^ 1].w += a;
			ret -= a;
			if (!ret)break;
		}
	}
	if (ret == flow)dis[st] = 0;
	return flow - ret;
}
int dinic(int st, int en) {
	int ans = 0;
	while (bfs(st, en)) {
		for (int s = st; s <= en; s++)//这里！！
			cur[s] = head[s];
		ans += dfs(st, en, inf);
	}
	return ans;
}
int v[maxn], e[maxn][3];
int main() {
	while (~scanf("%d%d", &n, &m)) {
		init();
		for (int i = 1; i <= n; i++) {
			scanf("%d", &v[i]);
		}
		for (int i = 1; i <= m; i++) {
			scanf("%d%d%d", &e[i][0], &e[i][1], &e[i][2]);
			add(i, e[i][0] + m, inf);
			add(i, e[i][1] + m, inf);
		}
		int st = 0, en = n + m + 1, sum = 0;
		for (int i = 1; i <= m; i++) {
			add(0, i, e[i][2]);
			sum += e[i][2];
		}
		for (int i = 1; i <= n; i++) {
			add(i + m, en, v[i]);
		}
		int t = dinic(st, en);
		printf("%d\n", sum - t);
	}
	return 0;
}

为修建代价）。然后照常跑就好了