POJ March of the Penguins

发布时间:2016-12-6 10:53:08 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"POJ March of the Penguins",主要涉及到POJ March of the Penguins方面的内容,对于POJ March of the Penguins感兴趣的同学可以参考一下。

和 那个蜥蜴的题目:UVA-live 3397 Leapin' Lizards真是很相似,好像这个还来得简单一点了。把企鹅呆的每个地方拆点,然后自己建立一条边,容量为能够起跳的数目,然后对于所有能够到达的地方同样建立边,容量为inf。求最大流即可,看到达每个点的企鹅数目是否等于所有企鹅数。PS:由于是要求所有能够聚集的点集,所有每次做完ISAP算法之后都应该将边集恢复一遍,便于下次再求最大流。 ISAP算法: #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <iostream> #include <cctype> #include <queue> #include <algorithm> #include <cmath> #define esp 1e-6 #define inf 0x0f0f0f0f #define print(a) printf("%d\n", (a)); #define bug puts("(****"); #define test freopen("in.txt","r",stdin); using namespace std; #define N 1000 #define M 100000 typedef struct { double x, y; int ni,mi; } Point; Point p[N]; struct EDGE { int i, c; EDGE *next, *ani; } *Edge[N], E[M], BE[M]; int Dfn[N], Now[N], cnt; int n, m, src, sink; void add(int i, int j, int c, EDGE &e1, EDGE &e2) { e1.i = j, e1.c = c, e1.next = Edge[i], e1.ani = &e2, Edge[i] = &e1; e2.i = i, e2.c = 0, e2.next = Edge[j], e2.ani = &e1, Edge[j] = &e2; } double cal(Point a, Point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int dblcmp(double x) { if(fabs(x) < esp) return 0; return x > 0? 1 : -1; } void init(void) { memset(Edge, 0, sizeof(Edge)); cnt = 0; } int ISAP(int s, int end, int flow) { if(s == end) return flow; int i, tab = n-1, vary, now = 0; for(EDGE *p =Edge[s]; p && flow - now; p = p->next) if(p->c) { if(Dfn[s] == Dfn[i = p->i] + 1) vary = ISAP(i, end, min(flow - now, p->c)), p->c -= vary, now += vary, p->ani->c += vary; if(p->c) tab = min(tab, Dfn[i]); if(Dfn[src] == n) return now; } if(now == 0) { if(--Now[Dfn[s]] == 0) Dfn[src] = n; Now[Dfn[s] = tab +1]++; } return now; } int Max_flow(int s, int end) { memset(Dfn, 0, sizeof(Dfn)); memset(Now, 0, sizeof(Now)); Now[0] = n; int ret = 0; for(; Dfn[s] < n;) { ret += ISAP(s, end, inf); } return ret; } void Restore(void) { for(int i = 0; i < cnt; i++) E[i] = BE[i]; } int main(void) { int T; double d; for(int t = scanf("%d", &T); t <= T; t++) { init(); int tot = 0; for(int i = scanf("%d%lf", &n, &d) - 2; i < n; i++) { scanf("%lf%lf%d%d", &p[i].x, &p[i].y, &p[i].ni, &p[i].mi); tot += p[i].ni; add(2*i, 2*i^1, p[i].mi, E[cnt], E[cnt + 1]); BE[cnt] = E[cnt], BE[cnt + 1] = E[cnt + 1]; cnt += 2; add(2*n, 2*i, p[i].ni, E[cnt], E[cnt + 1]); BE[cnt] = E[cnt], BE[cnt + 1] = E[cnt + 1]; cnt += 2; } for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i - j) { double dist = cal(p[i], p[j]); if(dblcmp(d - dist) >= 0) { add(2*i^1, 2*j, inf, E[cnt], E[cnt + 1]); BE[cnt] = E[cnt], BE[cnt + 1] = E[cnt + 1]; cnt += 2; add(2*j^1, 2*i, inf, E[cnt], E[cnt + 1]); BE[cnt] = E[cnt], BE[cnt + 1] = E[cnt + 1]; cnt += 2; } } int ans[N]; int top = -1; int temp = n; src = 2*n; n = 2*n+1; for(int i = 0; i < temp; i++) { sink = 2*i; if( tot == Max_flow(src, sink)) ans[++top] = i; Restore(); } if(top >= 0) { printf("%d", ans[0]); for(int i = 1; i <= top; i++) printf(" %d", ans[i]); } else printf("-1"); puts(""); } return 0; }

上一篇:matlab gui 以及常用函数
下一篇:poj 3281 Dining (最大流)

相关文章

相关评论