在n行m列的地图上进行植物大战僵尸游戏. 每个格子上都有植物. 僵尸从右边进入地图, 只能直走, 只能依次吃植物. 每株植物有一个整数, 表示僵尸吃掉它的收益. 每株植物有一个攻击位置集合, 攻击力无穷 (一击致命), 零冷却时间; 保证植物不能攻击自己所在位置. 求僵尸的最大收益 (可以选择不进行任何攻击). (1≤n≤20, 1≤m≤30, -10000≤Score≤10000) 一株植物被另一株植物所保护 (攻击/地理位置), 要吃掉它, 就必须吃掉它的保护者. 要求收益最大. 这几乎是一个最大权闭合图模型.
| 最大权闭合图问题可以用最小割求解: |
| 源点向正权点连边, 容量等于点权; 负权点向汇点连边, 容量等于点权的相反数; 原图上的边保留, 容量等于正无穷. 求出最小割[S, T], S-{s}即为选择的点集; 正权点权和-c[S,T] = 答案. |
| 称容量有限的割为简单割. |
| 一个简单割对应一个可行解 (S-{s}为选择的点集). 因为原图中一个点和它的后继之间的边在网络中的容量为inf, 简单割一定不含这条边, 所以两者始终连通, 只能同时属于S或同时属于T. |
| 一个可行解对应一个简单割 (V1+{s}=S). 一个可行解一定对应一个割. 这个割不含容量为inf的边, 否则这条边连接的两点一个被选, 一个不被选, 而它们在原图中有边相连. |
| 先假设所有正权点都选择, 负权点都不选, 那么答案等于正权点权和. s与一个正权点的连边割掉, 表示这个点不选, 减掉这条边的容量. 一个负权点与t的连边割掉, 表示这个点选择, 减掉这条边的容量. 于是, 答案=正权点权和-c[S,T]. 为了最大化答案, 就得最小化c[S,T], 所以最小割为最优解. |
| 以上参考自 胡伯涛2007年国家集训队论文 <最小割模型在信息学竞赛中的应用>. |
对于原图中的某个强连通分量, 闭合子图要么包含它整个, 要么其中一个点都不含. 但是本题植物攻击力无穷且冷却时间为零, 这意味着一些植物的保护关系成环, 则它们是无敌的.
然后我写了个Tarjan去掉点数大于1的强连通分量QAQ 这是不对的, 因为被环中植物保护的其他植物也是无敌的......也就是说, - 如果某点在环中, 则它被ban掉 - 如果某点的后继被ban掉, 那么它也被ban掉
写一个DFS, 讨论一下某边是树边, 前向边, 后向边, 横向边, 还是指向另一棵DFS树的边即可.
也可以用拓扑排序那种判断度数的算法. ban掉所有不能被拓扑排序的点. DFS相当于拓扑排序的DFS算法.
然后还是WA, 因为每轮DFS增广之前, 把当前弧数组的初始化搞错......
const int N = 20, M = 30, inf = 1e8;
namespace MinimumCut {
const int N = 602;
struct Edge {
int v, c;
};
vector<Edge> E;
vector<int> adj[N];
inline void add(int u, int v, int c)
{
adj[u].push_back(E.size());
E.push_back((Edge){v, c});
adj[v].push_back(E.size());
E.push_back((Edge){u, 0});
}
int s, t, n;
int lv[N], cur[N];
bool bfs()
{
queue<int> Q;
Q.push(s);
fill_n(lv, n, -1);
lv[s] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
rep (i, 0, adj[u].size()) {
Edge& e = E[adj[u][i]];
if (e.c && lv[e.v] == -1) {
lv[e.v] = lv[u] + 1;
Q.push(e.v);
}
}
}
return lv[t] != -1;
}
int dfs(int u, int f)
{
if (u == t) return f;
int res = f;
for (int& i = cur[u]; i < (int)adj[u].size(); ++i) {
Edge& e = E[adj[u][i]];
if (lv[e.v] == lv[u] + 1 && e.c) {
int d = dfs(e.v, min(res, e.c));
res -= d;
e.c -= d;
E[adj[u][i]^1].c += d;
if (!res) break;
}
}
return f - res;
}
int minimum_cut(int _s, int _t, int _n)
{
s = _s, t = _t, n = _n;
int f = 0;
while (bfs()) {
fill_n(cur, n, 0);
f += dfs(s, inf);
}
return f;
}
}
using MinimumCut::add;
#define S (n*m)
#define T (n*m+1)
#define P(i, j) ((i)*m+(j))
bool ban[N*M], vis[N*M], fin[N*M];
int w[N*M];
vector<int> adj[N*M];
void dfs(int u)
{
vis[u] = true;
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (vis[v]) {
if (!fin[v])
ban[u] = true;
} else
dfs(v);
ban[u] |= ban[v];
}
fin[u] = true;
}
inline void add_edge(int u, int v)
{
adj[u].push_back(v);
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
rep (i, 0, n) {
rep (j, 0, m) {
int k, now = P(i, j);
scanf("%d%d", &w[now], &k);
while (k--) {
int x, y;
scanf("%d%d", &x, &y);
add_edge(P(x, y), now);
}
if (j != m-1)
add_edge(now, now+1);
}
}
rep (i, 0, n*m)
if (!vis[i])
dfs(i);
int sum = 0;
rep (i, 0, n*m) if (!ban[i]) {
if (w[i] > 0) {
sum += w[i];
add(S, i, w[i]);
} else
add(i, T, -w[i]);
rep (j, 0, adj[i].size()) {
int k = adj[i][j];
if (!ban[k])
add(i, k, inf);
}
}
printf("%d\n", sum - MinimumCut::minimum_cut(S, T, n*m + 2));
return 0;
}