「JSOI2014」电信网络

「JSOI2014」电信网络

传送门

一个点选了就必须选若干个点，最大化点权之和，显然最大权闭合子图问题。

一个点向它范围内所有点连边，直接跑最大权闭合子图即可。

参考代码：

#include <cstring>

#include <cstdio>

#define rg register

#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

template < class T > inline T min(T a, T b) { return a < b ? a : b; }

template < class T > inline void read(T& s) {

    s = 0; int f = 0; char c = getchar();

    while ('0' > c || c > '9') f |= c == '-', c = getchar();

    while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar();

    s = f ? -s : s;

}

const int _ = 502, __ = 3e5 + 5, INF = 2147483647;

int tot = 1, head[_]; struct Edge { int v, w, nxt; } edge[__ << 1];

inline void Add_edge(int u, int v, int w) { edge[++tot] = (Edge) { v, w, head[u] }, head[u] = tot; }

inline void Link(int u, int v, int w) { Add_edge(u, v, w), Add_edge(v, u, 0); }

int n, X[_], Y[_], R[_], S[_];

int s, t, dep[_], cur[_], hd, tl, Q[_];

inline int bfs() {

    memset(dep, 0, sizeof (int) * (t - s + 1));

    hd = tl = 0, dep[Q[++tl] = s] = 1;

    while (hd < tl) {

    	int u = Q[++hd];

    	for (rg int i = head[u]; i; i = edge[i].nxt) {

	        int v = edge[i].v, w = edge[i].w;

	        if (dep[v] == 0 && w) dep[v] = dep[u] + 1, Q[++tl] = v;

	    }

    }

    return dep[t] > 0;

}

inline int dfs(int u, int flow) {

    if (u == t) return flow;

    for (rg int& i = cur[u]; i; i = edge[i].nxt) {

	    int v = edge[i].v, w = edge[i].w;

	    if (dep[v] == dep[u] + 1 && w) {

	        int res = dfs(v, min(flow, w));

	        if (res) { edge[i].w -= res, edge[i ^ 1].w += res; return res; }

	    }

    }

    return 0;

}

inline int Dinic() {

    int res = 0;

    while (bfs()) {

	    for (rg int i = s; i <= t; ++i) cur[i] = head[i];

	    while (int d = dfs(s, INF)) res += d;

    }

    return res;

}

int main() {

#ifndef ONLINE_JUDGE

    file("cpp");

#endif

    read(n), s = 0, t = n + 1;

    int ans = 0;

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

	    read(X[i]), read(Y[i]), read(R[i]), read(S[i]);

	    if (S[i] > 0) Link(s, i, S[i]), ans += S[i];

	    else if (S[i] < 0) Link(i, t, -S[i]);

    }

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

    	for (rg int j = 1; j <= n; ++j)

	        if (i != j && (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]) <= R[i] * R[i]) Link(i, j, INF);

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

    return 0;

}