题意: 在 X,Y 坐标系中有 N(N<=100) 个冰块... 有些冰块上有若干只企鹅.. 每只企鹅一次最多跳 M 距离.. 一个冰块在有 Mi 个企鹅离开.. 就会消失.. 问有哪些冰块可以作为集合点.. 就是所有企鹅都能成功到这个冰块上来.
这个题建图比较有意思.
把每块冰分成两个点 i 和 i+n. i 表示进入 i 冰块的点 (可以有无数企鹅过来, 所以从别的冰到 i 有边, 容量为 INF) i+n 表示从 i 冰块出去的点 (最多只能有 Mi 企鹅从这跳出去, 所以从 i 到 i+n 有边, 且容量为 Mi)
从源点 S 到 i 有边 (S, i, i 点初始企鹅数).
从 i 到 i+n 有边 (i, i+n, Mi). 表示第 i 块冰最多只有 Mi 个企鹅能跳走.
因为 i+n 表示的是第 i 个跳走的点, 所以如果冰块 i 和 j 之间的距离 <= 企鹅能跳跃的距离 M, 有边 (i+n, j, INF)
假设我们当前枚举第 x 块冰块作为集合点, 那么 (x 分成 x 和 x+n 两个点)x 点就是汇点 (不是 x+n 点哦), 我们只要计算到 x 点的流量是否 == 企鹅总数即可.
- #include<stdio.h>
- #include<string.h>
- #include<queue>
- #include<cmath>
- #define maxn 1000
- #define INF 0x3f3f3f3f
- using namespace std;
- struct e {
- int from, to, w, next;
- }edge[1000000];
- struct p {
- int x, y;
- }pos[10000];
- int ss, tt;
- int n;
- double d;
- int cur[maxn];
- int cont;
- int head[maxn];
- int map[maxn][maxn];
- int dis[maxn][maxn];
- int divv[maxn];
- int x[maxn], y[maxn], num[maxn], m[maxn];
- bool check(p a, p b) {
- double dis = sqrt(pow(fabs(a.x - b.x), 2) + pow(fabs(a.y - b.y), 2));
- if (dis <= d)
- return true;
- else
- return false;
- }
- void add(int u, int v, int w) {
- edge[cont].from = u;
- edge[cont].to = v;
- edge[cont].w = w;
- edge[cont].next = head[u];
- head[u] = cont++;
- }
- void makediv() {
- memset(divv, 0, sizeof(divv));
- divv[ss] = 1;
- queue<int> Q;
- Q.push(ss);
- while (!Q.empty()) {
- int u = Q.front();
- Q.pop();
- for (int i = head[u]; i != -1; i = edge[i].next) {
- int w = edge[i].w;
- int v = edge[i].to;
- if (divv[v] == 0 && w) {
- divv[v] = divv[u] + 1;
- Q.push(v);
- }
- }
- }
- }
- int DFS(int u, int maxflow, int tt) {
- if (u == tt)
- return maxflow;
- int ret = 0;
- for (int &i = cur[u]; i != -1; i = edge[i].next) {
- int v = edge[i].to;
- int w = edge[i].w;
- if (divv[v] == divv[u] + 1 && w) {
- int f = DFS(v, min(maxflow - ret, w), tt);
- edge[i].w -= f;
- edge[i ^ 1].w += f;
- ret += f;
- if (ret == maxflow)
- return ret;
- }
- }
- return ret;
- }
- int Dinic() {
- int ans = 0;
- while (1) {
- makediv();
- if (divv[tt] == 0)
- break;
- memcpy(cur, head, sizeof(head));
- ans += DFS(ss, INF, tt);
- }
- return ans;
- }
- void Build() {
- for (int i = 1; i <= n; i++) {
- add(ss, i, num[i]);
- add(i, ss, 0);
- add(i, i + n, m[i]);
- add(i + n, i, 0);
- }
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= n; j++) {
- if (i == j)
- continue;
- if (check(pos[i], pos[j])) {
- add(i + n, j, INF);
- add(j, i + n, 0);
- }
- }
- }
- }
- int main(void) {
- int t;
- int p_n;
- scanf("%d", &t);
- while (t--) {
- bool flag = false;
- ss = 0;
- p_n = 0;
- scanf("%d%lf", &n, &d);
- memset(head, -1, sizeof(head));
- for (int i = 1; i <= n; i++) {
- scanf("%d%d%d%d", &x[i], &y[i], &num[i], &m[i]);
- if (num)
- p_n += num[i];
- pos[i].x = x[i];
- pos[i].y = y[i];
- }
- vector<int> V;
- for (int i = 1; i <= n; i++) {
- tt = i;
- cont = 0;
- memset(head, -1, sizeof(head));
- Build();
- if (Dinic() == p_n) {
- flag = true;
- V.push_back(i - 1);
- }
- }
- if (!flag)
- printf("-1\n");
- else {
- for (int i = 0; i < (int)V.size(); i++)
- if (i != V.size() - 1)
- printf("%d", V[i]);
- else
- printf("%d\n", V[i]);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2582305.html