题意：给你一张图，每个节点保护若干节点。
当一个节点不被保护的时候，你就可以gay掉它。
gay每个节点都有收益(可能为负)，求最大总收益。
解：首先发现是一个最大权闭合子图。
把保护关系变成被保护，那么gay每个节点就必须gay每个保护它的节点。
然后发现有个小问题：有环。
于是我们tarjan求强连通分量然后删点。最后最大权闭合子图。
这里我删点删的十分暴力......(反正点不多)
注意：删点的时候，如果它权值为正，要在sum里面减去它的权值。
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <stack> const int N = , M = , INF = 0x3f3f3f3f; struct Edge {
int nex, v, c;
}edge[M << ], _edge[M]; int top = , _top; int e[N], d[N], _e[N];
std::queue<int> Q;
std::stack<int> S;
int dfn[N], low[N], num, fr[N], scc_cnt, scc_siz[N], vis[N], val[N], sum; void tarjan(int x) {
dfn[x] = low[x] = ++num;
S.push(x);
for(int i = _e[x]; i; i = _edge[i].nex) {
int y = _edge[i].v;
if(!dfn[y]) {
tarjan(y);
low[x] = std::min(low[x], low[y]);
}
else if(!fr[y]) {
low[x] = std::min(low[x], dfn[y]);
}
}
if(low[x] == dfn[x]) {
scc_cnt++;
int y;
do {
y = S.top();
S.pop();
fr[y] = scc_cnt;
scc_siz[scc_cnt]++;
} while(y != x);
}
return;
} inline void add(int x, int y, int z) {
top++;
edge[top].v = y;
edge[top].c = z;
edge[top].nex = e[x];
e[x] = top; top++;
edge[top].v = x;
edge[top].c = ;
edge[top].nex = e[y];
e[y] = top;
return;
} inline void _add(int x, int y) {
_top++;
_edge[_top].v = y;
_edge[_top].nex = _e[x];
_e[x] = _top;
return;
} void del(int x) {
vis[x] = ;
if(val[x] > ) {
sum -= val[x];
}
for(int i = e[x]; i; i = edge[i].nex) {
edge[i].c = edge[i ^ ].c = ;
}
for(int i = _e[x]; i; i = _edge[i].nex) {
int y = _edge[i].v;
if(!vis[y]) {
del(y);
}
}
e[x] = _e[x] = ;
return;
} inline bool BFS(int s, int t) {
memset(d, , sizeof(d));
d[s] = ;
Q.push(s);
while(!Q.empty()) {
int x = Q.front();
Q.pop();
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[y]) {
continue;
}
d[y] = d[x] + ;
Q.push(y);
}
}
return d[t];
} int DFS(int x, int t, int maxF) {
if(x == t) {
return maxF;
}
int ans = ;
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
if(!edge[i].c || d[x] + != d[y]) {
continue;
}
int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
if(!temp) {
d[y] = INF;
}
ans += temp;
edge[i].c -= temp;
edge[i ^ ].c += temp;
if(ans == maxF) {
break;
}
}
return ans;
} inline int solve(int s, int t) {
int ans = ;
while(BFS(s, t)) {
ans += DFS(s, t, INF);
}
return ans;
} int m;
inline int id(int x, int y) {
return (x - ) * m + y;
} int main() { int n;
scanf("%d%d", &n, &m);
int s = n * m + , t = n * m + ;
for(int i = ; i <= n; i++) {
for(int j = ; j <= m; j++) {
int x, y, z;
scanf("%d", &x);
val[id(i, j)] = x;
if(x > ) {
add(s, id(i, j), x);
sum += x;
}
else if(x < ) {
add(id(i, j), t, -x);
}
scanf("%d", &z);
for(int k = ; k <= z; k++) {
scanf("%d%d", &x, &y);
x++;
y++;
add(id(x, y), id(i, j), INF);
_add(id(i, j), id(x, y));
}
if(j < m) {
add(id(i, j), id(i, j + ), INF);
_add(id(i, j + ), id(i, j));
}
}
}
for(int i = ; i <= n * m; i++) {
if(!dfn[i]) {
tarjan(i);
}
}
for(int i = ; i <= n * m; i++) {
if(scc_siz[fr[i]] > && !vis[i]) {
del(i);
}
}
printf("%d", sum - solve(s, t));
return ;
}
AC代码