首页 > 代码库 > [BZOJ 1066] [SCOI2007] 蜥蜴 【最大流】
[BZOJ 1066] [SCOI2007] 蜥蜴 【最大流】
题目链接：BZOJ - 1066
题目分析
题目限制了高度为 x 的石柱最多可以有 x 只蜥蜴从上面跳起，那么就可以用网络流中的边的容量来限制。我们把每个石柱看作一个点，每个点拆成 i1, i2，从 i1 到 i2 连一条边，容量为这个石柱 i 的高度，即跳跃次数限制。来到这个石柱就是向 i1 连边，从这个石柱跳起就是从 i2 向外连边，这样只要从石柱 i 跳起就一定会消耗 i1 到 i2 的边的容量。如果 i 有蜥蜴，就从 S 到 i1 连一条容量为 1 的边，如果从石柱 i 能跳出边界，就从 i2 到 T 连 INF 的边。如果从石柱 i 能跳到石柱 j ，就从 i2 到 j1 连 INF 的边。这样求出的最大流就是能够跳出的蜥蜴的数量。
题目还限制了“任何时刻不能有两只蜥蜴在同一个石柱上”，但是想一想就会发现，这个限制其实并没有影响，只要我们按照合适的顺序让蜥蜴们先后跳跃，就一样可以让那些应该跳出的蜥蜴跳出。
另外，题目要求输出不能跳出的蜥蜴的数量，结果我直接输出了能跳出的数量...于是对着数据调了1h...最后发现是输出的东西不对...QAQ
代码
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <cstring> using namespace std; const int MaxR = 20 + 5, MaxN = 400 * 2 + 5, MaxM = 500000 * 2 + 5, INF = 0x3fffffff; int n, m, Dis, Top, S, T, Tot, Ans, Sum;int Num[MaxN], d[MaxN]; bool Be[MaxR][MaxR]; char Str[MaxR]; struct Edge { int v, w; Edge *Next, *Other;} E[MaxM], *P = E, *Point[MaxN], *Last[MaxN]; inline void AddEdge(int x, int y, int z) { Edge *Q = ++P; ++P; P -> v = y; P -> w = z; P -> Next = Point[x]; Point[x] = P; P -> Other = Q; Q -> v = x; Q -> w = 0; Q -> Next = Point[y]; Point[y] = Q; Q -> Other = P;} struct ES{ int x, y, z; ES() {} ES(int a, int b, int c) { x = a; y = b; z = c; }} JF[MaxN]; typedef double DB; bool Check(int x, int y) { if ((x - 1) < Dis || (y - 1) < Dis) return true; if ((n - x) < Dis || (m - y) < Dis) return true; return false;} inline DB Sqr(DB x) {return x * x;} DB Calc(DB x, DB y, DB xx, DB yy) { return sqrt(Sqr(x - xx) + Sqr(y - yy));} inline int gmin(int a, int b) {return a < b ? a : b;} int DFS(int Now, int Flow) { if (Now == T) return Flow; int ret = 0; for (Edge *j = Last[Now]; j; j = j -> Next) { if (j -> w && d[Now] == d[j -> v] + 1) { Last[Now] = j; int p = DFS(j -> v, gmin(j -> w, Flow - ret)); j -> w -= p; j -> Other -> w += p; ret += p; if (ret == Flow) return ret; } } if (d[S] >= Tot) return ret; if (--Num[d[Now]] == 0) d[S] = Tot; ++Num[++d[Now]]; Last[Now] = Point[Now]; return ret;} int main() { scanf("%d%d%d", &n, &m, &Dis); Top = 0; for (int i = 1; i <= n; ++i) { scanf("%s", Str); for (int j = 1; j <= m; ++j) { if (Str[j - 1] != ‘0‘) { JF[++Top] = ES(i, j, Str[j - 1] - ‘0‘); } } } Sum = 0; for (int i = 1; i <= n; ++i) { scanf("%s", Str); for (int j = 1; j <= m; ++j) { if (Str[j - 1] == ‘L‘) { Be[i][j] = true; ++Sum; } else Be[i][j] = false; } } S = Top * 2 + 1; T = S + 1; Tot = T; for (int i = 1; i <= Top; ++i) { int xx = JF[i].x, yy = JF[i].y; AddEdge(i, Top + i, JF[i].z); if (Check(xx, yy)) AddEdge(Top + i, T, INF); if (Be[xx][yy]) AddEdge(S, i, 1); for (int j = 1; j <= Top; ++j) { if (j == i) continue; if (Calc(xx, yy, JF[j].x, JF[j].y) <= (DB)Dis) AddEdge(Top + i, j, INF); } } for (int i = 1; i <= Tot; ++i) Last[i] = Point[i]; memset(Num, 0, sizeof(Num)); Num[0] = Tot; memset(d, 0, sizeof(d)); Ans = 0; while (d[S] < Tot) Ans += DFS(S, INF); printf("%d\n", Sum - Ans); return 0;}
[BZOJ 1066] [SCOI2007] 蜥蜴 【最大流】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。