题意：给你一张图，每个节点保护若干节点。
当一个节点不被保护的时候，你就可以gay掉它。
gay每个节点都有收益(可能为负)，求最大总收益。
解：首先发现是一个最大权闭合子图。
把保护关系变成被保护，那么gay每个节点就必须gay每个保护它的节点。
然后发现有个小问题：有环。
于是我们tarjan求强连通分量然后删点。最后最大权闭合子图。
这里我删点删的十分暴力......(反正点不多)
注意：删点的时候，如果它权值为正，要在sum里面减去它的权值。
1 #include <cstdio> 2 #include <algorithm> 3 #include <queue> 4 #include <cstring> 5 #include <stack> 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<int> Q; 15 std::stack<int> 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 }