YJQQQAQ's Blog

题解：

       一个不能更裸的最小割。先假设所有的人都被选中，然后就是割掉一些边（割边的意义，对于中转站来说是修建中转站，对于人群来说是放弃这个人群的收益），使得图合法。最后就是总答案-最大流。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <queue>
#define INF 1000000007
using namespace std;
int n,m;
const int MAXN = 60010;
struct EDGE {
	int l,r,c;
	EDGE (int _l = 0,int _r = 0,int _c = 0) {
		l = _l;
		r = _r;
		c = _c;
	}
} e[MAXN << 3];
int ecnt  =0;
vector<int> g[MAXN];

void addedge(int l,int r,int c) {
	e[ecnt] = EDGE (l,r,c);
	g[l].push_back(ecnt);
	ecnt++;
}
void adde(int l,int r,int c) {
	addedge(l,r,c);
	addedge(r,l,0);
}
int ans;
int src = 0,sink;

int dis[MAXN];
queue<int> q;
bool bfs() {
	q.push(src);
	for (int i=src;i<=sink;i++) {
		dis[i] = INF;
	}
	dis[src] = 0;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i=0;i<g[cur].size();i++) {
			int add = g[cur][i];
			int to = e[add].r;
			if (dis[to] == INF && e[add].c) {
				dis[to] = dis[cur] + 1;
				q.push(to);
			}
		}
	}
	return dis[sink] != INF;
}

int dfs(int cur,int flow) {
	if (cur == sink) return flow;
	int ret = flow;
	for (int i=0;i<g[cur].size() && ret;i++) {
		int add = g[cur][i];
		int to = e[add].r;
		if (dis[to] == dis[cur] + 1 && e[add].c) {
			int delta = dfs(to,min(ret,e[add].c));
			ret -= delta;
			e[add].c -= delta;
			e[add^1].c += delta;
		}
	}
	return flow - ret;
}

int main() {
#ifdef YJQ_LOCAL
	freopen(".in","r",stdin);
#endif
	scanf("%d%d",&n,&m);
	sink = n + m + 1;
	for (int i=1;i<=n;i++) {
		int v;
		scanf("%d",&v);
		adde(src,i,v);
	}
	for (int i=1;i<=m;i++) {
		int cur = i + n;
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		adde(cur,sink,c);
		ans += c;
		adde(a,cur,INF);
		adde(b,cur,INF);
	}
	while (bfs()) ans -=dfs(src,INF);
    printf("%d\n",ans);
}