题意

给出一个二分图，求在选的点尽量多的前提下的最大点权独立集。输出方案。

思路

对于选点最多的前提，将每个点权加上\(inf\)，这样子选的点多的方案优先被考虑。
将二分图原图的每条边连向S、T，容量分别为端点的点权。
求解最小割即可，即选哪个端点较优。

输出方案在残量网络上搜索即可。
具体地，从S出发遍历能到的点，记为\(S\)集合。
剩下到不了的点记为\(T\)集合。
对于\(e=(u,v),u\in S, v\in T\)即为最小割上的边。

代码

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long

const int inf = 1e6;

int n, m, sum, tot, S, E, cnt, ans;
int f[301][301], edge[50001], lev[301], cur[301], scc[301];
int a[301], ver[50001], next[50001], head[301], line[301], v[301], sel[301], col[301];

void add(int u, int v, int f) {
	ver[++tot] = v, next[tot] = head[u], edge[tot] = f, head[u] = tot;
	ver[++tot] = u, next[tot] = head[v], edge[tot] = 0, head[v] = tot;
}

void dfs(int p, int c) {
	col[p] = c;
	for (int i = head[p]; i; i = next[i])
		if (!col[ver[i]])
			dfs(ver[i], 3 - c);
}

int dfs1() {
	std::queue<int> q;
	for (int i = 1; i <= E; i++)
		lev[i] = 0, cur[i] = head[i];
	lev[S] = 1;
	q.push(S);
	int v;
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; i; i = next[i])
			if (edge[i] && !lev[v = ver[i]]) {
				lev[v] = lev[u] + 1;
				q.push(v);
			}
	}
	return lev[E];
}

int dinic(int u, int flow) {
	if (u == E)
		return flow;
	int res = 0, delta, v;
	for (int &e = cur[u]; e; e = next[e]) 
		if (edge[e] && lev[u] < lev[v = ver[e]]) {
			delta = dinic(v, std::min(edge[e], flow - res));
			if (delta) {
				edge[e] -= delta;
				edge[e ^ 1] += delta;
				res += delta;
				if (res == flow)
					break;
			}
		}
	if (res != flow)
		lev[u] = 0;
	return res;
}

void dfs2(int p) {
	for (int i = head[p], y; i; i = next[i])
		if (!scc[y = ver[i]] && edge[i])
			scc[y] = 1, dfs2(y);
}

signed main() {
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]), a[i] += inf, sum += a[i];
	for (int i = 1, x, y; i <= m; i++)
		scanf("%lld %lld", &x, &y), f[x][y] = f[y][x] = 1, add(x, y, 0);
	for (int i = 1; i <= n; i++)
		if (!col[i])
			dfs(i, 1);
	memset(head, 0, sizeof(head));
	tot = 1;
	S = n + 1, E = n + 2;
	for (int i = 1; i <= n; i++)
		if (col[i] == 1) {
			for (int j = 1; j <= n; j++)
				if (col[j] == 2 && f[i][j])
					add(i, j, 1000000000);
			add(S, i, a[i]);
		} else
			add(i, E, a[i]);
	while (dfs1())
		ans += dinic(S, 1000000000);
	dfs2(S);
	ans = 0;
	for (int i = 1; i <= n; i++)
		if ((col[i] - 1 ^ scc[i]) == 1)//根据染色情况判断是否选择了这个点
			ans += a[i] - inf, cnt++;
	printf("%lld %lld\n", cnt, ans);
	for (int i = 1; i <= n; i++)
		printf("%lld", col[i] - 1 ^ scc[i]);
}