[NOI2009] 植物大戰(zhàn)僵尸

在n*m的地圖當(dāng)中，每個(gè)位置都有一個(gè)植物，每個(gè)植物有一個(gè)價(jià)值，這個(gè)價(jià)值可能是正數(shù)也可能是負(fù)數(shù)。每個(gè)植物可能有幾個(gè)攻擊的位置，只有在除掉這個(gè)植物之后才可以到那幾個(gè)位置去。作為僵尸，只能從右往左攻擊，每次可以除掉一個(gè)植物，找到方案使除掉的植物總價(jià)值最大。
數(shù)據(jù)范圍n<=20 m<=30

最大權(quán)閉合子圖入門題，用最小割來解決。

如果我們要除掉一個(gè)植物的話，那么首先我們需要除掉的是在這個(gè)植物右邊的所有植物以及所有可以攻擊到這個(gè)位置的植物，也就是，如果選擇了這個(gè)植物，那么這些植物就都得選擇。這就是一個(gè)最大權(quán)閉合子圖問題，可以用最小割來進(jìn)行求解。

按照最小割的一般方法，先把所有的能選的都選上，再去割那些不合法的。在這個(gè)問題上，首先將所有的正數(shù)的植物全部選了，計(jì)算一個(gè)sum，然后由源點(diǎn)向所有正數(shù)點(diǎn)進(jìn)行連邊，邊容量為植物價(jià)值，由所有的負(fù)數(shù)點(diǎn)向匯點(diǎn)進(jìn)行連邊，邊容量為植物價(jià)值的相反數(shù)。然后將閉合子圖的關(guān)系建出來，容量為inf，求出最小割就可以了。

這樣的原理在于：首先我們是默認(rèn)選擇了所有的正數(shù)，那么除了這些植物以外，基本上還有很多負(fù)數(shù)的植物要選擇，這就要作出抉擇了，要么取消一個(gè)正數(shù)的植物，就是割源點(diǎn)的邊，要么就是選擇它并且承擔(dān)需要選擇的負(fù)數(shù)的植物，就是割匯點(diǎn)的邊。最小割的值和sum的價(jià)值取差值就是答案。

這個(gè)問題中，還要考慮到有幾個(gè)植物搞小團(tuán)體互相保，就要直接排除它們。這要用到拓?fù)渑判蛉サ舡h(huán)，注意拓?fù)渑判虻娜攵仁菑挠业阶蟮?#xff0c;而建邊是從左到右的。

這個(gè)代碼只得了90，有一個(gè)點(diǎn)T了，感覺應(yīng)該是要把環(huán)除去重新建邊，再跑網(wǎng)絡(luò)流，不過我寫累了，就這樣吧。

const int N = 610, M = 1e6, inf = 1e9 + 7; int n, m, s, t, sum = 0; int a[N], head[N], now[N], num = -1, dis[N], in[N]; bool vis[N], tp[N];struct edge {int nxt, to, flow; }; edge e[M];void addEdge(int x, int y, int z) {e[++ num].nxt = head[x];head[x] = num;e[num].to = y;e[num].flow = z; }inline int getNum(int x, int y) {return x * m + y; }bool bfs() {for (int i = 0; i <= n * m + 1; i ++)dis[i] = inf;dis[s] = 0;queue <int> q;q.push(s);while (!q.empty()){int x = q.front(); q.pop();for (int i = head[x]; i != -1; i = e[i].nxt){int to = e[i].to;if (dis[to] > dis[x] + 1 && e[i].flow > 0 && tp[to]){dis[to] = dis[x] + 1;q.push(to);}}}if (dis[t] == inf) return false;return true; }int dfs(int x, int flow) {if (vis[x] || !tp[x])return 0;vis[x] = 1;if (x == t)return flow;for (int i = now[x]; i != -1; i = e[i].nxt){now[x] = i;int to = e[i].to;if (dis[to] == dis[x] + 1 && e[i].flow > 0){int val = dfs(to, min(flow, e[i].flow));if (val > 0){e[i].flow -= val;e[i ^ 1].flow += val;return val;}}}return 0; }void dinic(int x, int y) {s = x; t = y;while (bfs()){for (int i = 0; i <= n * m + 1; i ++){now[i] = head[i];vis[i] = 0;}int val = 0;while (val = dfs(s, inf)){sum -= val;}} }int main() {//freopen ("in.txt", "r", stdin);memset (head, -1, sizeof (head));n = read(); m = read();for (int i = 0; i < n; i ++)for (int j = 0; j < m; j ++){int temp = getNum(i, j);a[temp] = read();if (j < m - 1){addEdge(temp, temp + 1, inf);addEdge(temp + 1, temp, 0);in[temp] ++;}int k = read();while (k --){int x = read(), y = read();int temp1 = getNum(x, y);addEdge(temp1, temp, inf);addEdge(temp, temp1, 0);in[temp1] ++;}}int cnt = 0;queue <int> q;for (int i = 0; i < n * m; i ++)if (!in[i])q.push(i);while (!q.empty()){int x = q.front(); q.pop();tp[x] = 1;for (int i = head[x]; i != -1; i = e[i].nxt){int to = e[i].to;in[to] --;if (!in[to])q.push(to);}}for (int i = 0; i < n * m; i ++)if (tp[i]){if (a[i] > 0){addEdge(n * m, i, a[i]);addEdge(i, n * m, 0);sum += a[i];}if (a[i] < 0){addEdge(i, n * m + 1, -a[i]);addEdge(n * m + 1, i, 0);}}tp[n * m] = tp[n * m + 1] = 1;dinic(n * m, n * m + 1);cout << sum;return 0; }

總結(jié)

以上是生活随笔為你收集整理的[NOI2009] 植物大战僵尸的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。