题意：给你一张图，每个节点保护若干节点。
当一个节点不被保护的时候，你就可以gay掉它。
gay每个节点都有收益(可能为负)，求最大总收益。
解：首先发现是一个最大权闭合子图。
把保护关系变成被保护，那么gay每个节点就必须gay每个保护它的节点。
然后发现有个小问题：有环。
于是我们tarjan求强连通分量然后删点。最后最大权闭合子图。
这里我删点删的十分暴力......(反正点不多)
注意：删点的时候，如果它权值为正，要在sum里面减去它的权值。
1 #include2 #include 3 #include 4 #include 5 #include 6 7 const int N = 1010, M = 1000010, INF = 0x3f3f3f3f; 8 9 struct Edge { 10 int nex, v, c; 11 }edge[M << 1], _edge[M]; int top = 1, _top; 12 13 int e[N], d[N], _e[N]; 14 std::queue Q; 15 std::stack S; 16 int dfn[N], low[N], num, fr[N], scc_cnt, scc_siz[N], vis[N], val[N], sum; 17 18 void tarjan(int x) { 19 dfn[x] = low[x] = ++num; 20 S.push(x); 21 for(int i = _e[x]; i; i = _edge[i].nex) { 22 int y = _edge[i].v; 23 if(!dfn[y]) { 24 tarjan(y); 25 low[x] = std::min(low[x], low[y]); 26 } 27 else if(!fr[y]) { 28 low[x] = std::min(low[x], dfn[y]); 29 } 30 } 31 if(low[x] == dfn[x]) { 32 scc_cnt++; 33 int y; 34 do { 35 y = S.top(); 36 S.pop(); 37 fr[y] = scc_cnt; 38 scc_siz[scc_cnt]++; 39 } while(y != x); 40 } 41 return; 42 } 43 44 inline void add(int x, int y, int z) { 45 top++; 46 edge[top].v = y; 47 edge[top].c = z; 48 edge[top].nex = e[x]; 49 e[x] = top; 50 51 top++; 52 edge[top].v = x; 53 edge[top].c = 0; 54 edge[top].nex = e[y]; 55 e[y] = top; 56 return; 57 } 58 59 inline void _add(int x, int y) { 60 _top++; 61 _edge[_top].v = y; 62 _edge[_top].nex = _e[x]; 63 _e[x] = _top; 64 return; 65 } 66 67 void del(int x) { 68 vis[x] = 1; 69 if(val[x] > 0) { 70 sum -= val[x]; 71 } 72 for(int i = e[x]; i; i = edge[i].nex) { 73 edge[i].c = edge[i ^ 1].c = 0; 74 } 75 for(int i = _e[x]; i; i = _edge[i].nex) { 76 int y = _edge[i].v; 77 if(!vis[y]) { 78 del(y); 79 } 80 } 81 e[x] = _e[x] = 0; 82 return; 83 } 84 85 inline bool BFS(int s, int t) { 86 memset(d, 0, sizeof(d)); 87 d[s] = 1; 88 Q.push(s); 89 while(!Q.empty()) { 90 int x = Q.front(); 91 Q.pop(); 92 for(int i = e[x]; i; i = edge[i].nex) { 93 int y = edge[i].v; 94 if(!edge[i].c || d[y]) { 95 continue; 96 } 97 d[y] = d[x] + 1; 98 Q.push(y); 99 }100 }101 return d[t];102 }103 104 int DFS(int x, int t, int maxF) {105 if(x == t) {106 return maxF;107 }108 int ans = 0;109 for(int i = e[x]; i; i = edge[i].nex) {110 int y = edge[i].v;111 if(!edge[i].c || d[x] + 1 != d[y]) {112 continue;113 }114 int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));115 if(!temp) {116 d[y] = INF;117 }118 ans += temp;119 edge[i].c -= temp;120 edge[i ^ 1].c += temp;121 if(ans == maxF) {122 break;123 }124 }125 return ans;126 }127 128 inline int solve(int s, int t) {129 int ans = 0;130 while(BFS(s, t)) {131 ans += DFS(s, t, INF);132 }133 return ans;134 }135 136 int m;137 inline int id(int x, int y) {138 return (x - 1) * m + y;139 }140 141 int main() {142 143 int n;144 scanf("%d%d", &n, &m);145 int s = n * m + 1, t = n * m + 2;146 for(int i = 1; i <= n; i++) {147 for(int j = 1; j <= m; j++) {148 int x, y, z;149 scanf("%d", &x);150 val[id(i, j)] = x;151 if(x > 0) {152 add(s, id(i, j), x);153 sum += x;154 }155 else if(x < 0) {156 add(id(i, j), t, -x);157 }158 scanf("%d", &z);159 for(int k = 1; k <= z; k++) {160 scanf("%d%d", &x, &y);161 x++;162 y++;163 add(id(x, y), id(i, j), INF);164 _add(id(i, j), id(x, y));165 }166 if(j < m) {167 add(id(i, j), id(i, j + 1), INF);168 _add(id(i, j + 1), id(i, j));169 }170 }171 }172 for(int i = 1; i <= n * m; i++) {173 if(!dfn[i]) {174 tarjan(i);175 }176 }177 for(int i = 1; i <= n * m; i++) {178 if(scc_siz[fr[i]] > 1 && !vis[i]) {179 del(i);180 }181 }182 printf("%d", sum - solve(s, t));183 return 0;184 }