• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 【网络流 最大点权独立集】我图呢

4小时前 3次浏览

## 代码

``````#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);
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])
} else
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 %lldn", cnt, ans);
for (int i = 1; i <= n; i++)
printf("%lld", col[i] - 1 ^ scc[i]);
}
``````