大概题意:
在南极的海洋上, 有一些企鹅站在一些浮冰上,这些企鹅想聚在一块,也就是到某块浮冰上聚会, 但是它们不想游泳,只想从一块浮冰跳到另一块上,自身的跳跃距离题中已经给出来了,然后是每个浮冰的坐标,该浮冰上已经有个多少个企鹅,以及浮冰的承受能力,所谓承受能力不是指能载动多少企鹅,题目中说了每个浮冰载企鹅是没有问题的,但是从浮冰往外跳会导致浮冰破损,这里的承受能力就是能跳出去多少次企鹅。
那么这题是一道网络流,题目要求的是最后能够成为聚会地点的浮冰标号,这里可以联想到需要枚举汇点,并且可以根据跳跃距离的限制N2枚举进行建边,但是每个浮冰的承受能力是点的容量,怎样转化为边的容量? 一般平时碰到的点的容量,可以直接连到汇点上, 要么你就拆点,将其变为两个点,中间的边容量就是点容量, 那么本题由于每块浮冰是可以去往多块浮冰的,所以直接连接汇点肯定不行,那么就需要进行拆点了
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <queue> #include <map> #include <set> #define eps 1e-5 #define MAXN 222 #define MAXM 55555 #define INF 100000007 using namespace std; struct node { int v; // vtex int c; // cacity int f; // current f in this arc int next, r; }edge[MAXM]; int dist[MAXN], nm[MAXN], src, des, n; int head[MAXN], e; void add(int x, int y, int c) { edge[e].v = y; edge[e].c = c; edge[e].f = 0; edge[e].r = e + 1; edge[e].next = head[x]; head[x] = e++; edge[e].v = x; edge[e].c = 0; edge[e].f = 0; edge[e].r = e - 1; edge[e].next = head[y]; head[y] = e++; } void rev_BFS() { int Q[MAXN], h = 0, t = 0; for(int i = 1; i <= n; ++i) { dist[i] = MAXN; nm[i] = 0; } Q[t++] = des; dist[des] = 0; nm[0] = 1; while(h != t) { int v = Q[h++]; for(int i = head[v]; i != -1; i = edge[i].next) { if(edge[edge[i].r].c == 0 || dist[edge[i].v] < MAXN)continue; dist[edge[i].v] = dist[v] + 1; ++nm[dist[edge[i].v]]; Q[t++] = edge[i].v; } } } void init() { e = 0; memset(head, -1, sizeof(head)); } int maxflow() { rev_BFS(); int u; int total = 0; int cur[MAXN], rpath[MAXN]; for(int i = 1; i <= n; ++i)cur[i] = head[i]; u = src; while(dist[src] < n) { if(u == des) // find an augmenting path { int tf = INF; for(int i = src; i != des; i = edge[cur[i]].v) tf = min(tf, edge[cur[i]].c); for(int i = src; i != des; i = edge[cur[i]].v) { edge[cur[i]].c -= tf; edge[edge[cur[i]].r].c += tf; edge[cur[i]].f += tf; edge[edge[cur[i]].r].f -= tf; } total += tf; u = src; } int i; for(i = cur[u]; i != -1; i = edge[i].next) if(edge[i].c > 0 && dist[u] == dist[edge[i].v] + 1)break; if(i != -1) // find an admissible arc, then Advance { cur[u] = i; rpath[edge[i].v] = edge[i].r; u = edge[i].v; } else // no admissible arc, then relabel this vtex { if(0 == (--nm[dist[u]]))break; // GAP cut, Important! cur[u] = head[u]; int mindist = n; for(int j = head[u]; j != -1; j = edge[j].next) if(edge[j].c > 0)mindist = min(mindist, dist[edge[j].v]); dist[u] = mindist + 1; ++nm[dist[u]]; if(u != src) u = edge[rpath[u]].v; // Backtrack } } return total; } int nt, v[MAXN], f[MAXN], out[MAXN]; double D, x[MAXN], y[MAXN]; double dis(int i, int j) { return sqrt((x[i] - x[j]) * (x[i]- x[j]) + (y[i] - y[j]) * (y[i] - y[j])); } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%lf", &nt, &D); int sum = 0; for(int i = 1; i <= nt; i++) { scanf("%lf%lf%d%d", &x[i], &y[i], &v[i], &f[i]); sum += v[i]; } src = 2 * nt + 1; n = 2 * nt + 1; int cnt = 0; for(int k = 1; k <= nt; k++) { init(); for(int i = 1; i <= nt; i++) for(int j = i + 1; j <= nt; j++) { if(dis(i, j) <= D) add(i + nt, j, INF), add(j + nt, i, INF); } for(int i = 1; i <= nt; i++) add(src, i, v[i]), add(i, i + nt, f[i]); des = k; int flow = maxflow(); //printf("%d\n", flow); if(flow == sum) out[cnt++] = k - 1; } if(!cnt) printf("-1\n"); else { for(int i = 0; i < cnt - 1; i++) printf("%d ", out[i]); printf("%d\n", out[cnt - 1]); } } return 0; }