urn 反向 map eof i++ clu sizeof n+1
反向最大闭合图 + topsort;
题解:
1. 从右往左链接相邻的植物;
2. 引有向边保护 --> 被保护;
3. 处理环;
4. 负权连 s,正权连 t;
5. 跑最大流;
- #include < iostream > #include < cstdio > #include < cstring > #define maxx 10000000 using namespace std;
- int read() {
- int f = 1,
- x = 0;
- char ch;
- ch = getchar();
- while (ch < '0' || ch > '9') {
- if (ch == ' - ') f = -1;
- ch = getchar();
- }
- while (ch >= '0' && ch <= '9') {
- x = (x << 1) + (x << 3) + ch - '0';
- ch = getchar();
- }
- return x * f;
- }
- int sum = 0;
- int st,
- ed;
- int n,
- m;
- int tot = 0;
- int vis[10000];
- int level[10000];
- int map[1000][1000];
- int ww[600][500];
- int c[100000];
- int v[100000];
- struct {
- int flow,
- next,
- y;
- }
- e[1000000];
- int len = 0;
- int re[1000000];
- int q[1000000],
- le[1000000],
- head,
- tail,
- lin[10000000];
- void init(int x, int y, int flow) {
- vis[y]++;
- e[++len].flow = flow;
- e[len].y = y;
- e[len].next = lin[x];
- lin[x] = len;
- re[len] = len + 1;
- e[++len].flow = 0;
- e[len].y = x;
- e[len].next = lin[y];
- lin[y] = len;
- re[len] = len - 1;
- return;
- }
- void initx() {
- st = ++tot;
- n = read();
- m = read();
- for (int i = 0; i <= n - 1; i++) for (int u = 0; u <= m - 1; u++) {
- map[i][u] = ++tot;
- if (u - 1 >= 0) init(map[i][u], map[i][u - 1], maxx);
- }
- ed = ++tot;
- for (int i = 0; i <= n - 1; i++) {
- for (int u = 0; u <= m - 1; u++) {
- v[map[i][u]] = read();
- int w = read();
- for (int z = 1; z <= w; z++) {
- int x,
- y;
- x = read();
- y = read();
- init(map[i][u], map[x][y], maxx);
- }
- }
- }
- }
- int f[1000000];
- void topsort() {
- head = 0;
- tail = 0;
- for (int i = map[0][0]; i <= map[n - 1][m - 1]; i++) if (vis[i] == 0) q[++tail] = i;
- while (head++<tail) {
- int x = q[head];
- for (int i = lin[x]; i; i = e[i].next) {
- if (e[i].flow <= 0) continue;
- int y = e[i].y;
- vis[y]--;
- if (vis[y] == 0) q[++tail] = y;
- }
- }
- for (int i = 1; i <= tail; i++) {
- f[q[i]] = 1;
- if (v[q[i]] >= 0) {
- init(q[i], ed, v[q[i]]),
- sum += v[q[i]];
- } else init(st, q[i], -v[q[i]]);
- }
- }
- bool makelevel() {
- f[st] = 1;
- f[ed] = 1;
- memset(level, -1, sizeof(level));
- head = 0;
- tail = 1;
- q[1] = st;
- level[st] = 0;
- while (head++<tail) {
- int x = q[head];
- for (int i = lin[x]; i; i = e[i].next) {
- int y = e[i].y;
- if (e[i].flow <= 0) continue;
- if (f[y] == 0) continue;
- if (level[y] == -1) {
- level[y] = level[x] + 1;
- q[++tail] = y;
- }
- }
- }
- //cout<<"s";
- return level[ed] != -1;
- }
- int maxlow(int x, int flow) {
- if (x == ed) return flow;
- int maax = 0;
- int d;
- for (int i = lin[x]; i && maax < flow; i = e[i].next) {
- int y = e[i].y;
- if (f[y] == 0) continue;
- if (e[i].flow <= 0) continue;
- if (level[y] != level[x] + 1) continue;
- if (d = maxlow(y, min(flow - maax, e[i].flow))) {
- maax += d;
- e[i].flow -= d;
- e[re[i]].flow += d;
- }
- }
- if (maax == 0) level[x] = -1;
- return maax;
- }
- int ans = 0;
- void dinic() {
- int d;
- while (makelevel()) while (d = maxlow(st, maxx)) {
- ans += d;
- }
- }
- int main() {
- initx();
- topsort();
- memset(q, 0, sizeof(q));
- dinic();
- cout << sum - ans << endl;
- return 0;
- }
【noi】植物大战僵尸
来源: http://www.bubuko.com/infodetail-2102546.html