蚂蚁

AcWing-375-蚂蚁

分析

见《进阶指南》第432页。

实现

#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 110, M = 20410;
struct edge {
    int to, next, c;
    double w;
};
edge e[M];
int idx, head[2 * N];
struct node {
    int x, y;
};
int n, s, t, max_flow, res[N];
double min_cost = 0;
node w[N], b[N];
double dis[2 * N];
int flow[2 * N], eid[2 * N];
bool mark[2 * N];

void add_edge (int u, int v, int c, double w) {
    e[idx].c = c;
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;

    e[idx].c = 0;
    e[idx].w = -w;
    e[idx].to = u;
    e[idx].next = head[v];
    head[v] = idx ++;
}
double get_dis (const node&a, const node& b) {
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
bool spfa () {
    memset(mark, 0, sizeof(mark));
    for (int i = 1; i <= t; ++ i) dis[i] = 1e12;
    dis[s] = 0;
    flow[s] = inf;
    queue<int> q;
    q.push(s);
    mark[s] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        mark[cur] = false;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, c = e[i].c;
            double w = e[i].w;
            if (c == 0) continue;
            if (dis[cur] + w < dis[to]) {
                dis[to] = dis[cur] + w;
                flow[to] = min(flow[cur], c);
                eid[to] = i;
                if (mark[to] == false) {
                    q.push(to);
                    mark[to] = true;
                }
            }
        }
    }
    return dis[t] != 1e12;
}
void update () {
    int cur = t;
    while (cur != s) {
        int i = eid[cur];
        e[i].c -= flow[t];
        e[i ^ 1].c += flow[t];
        cur = e[i ^ 1].to;
    }
    max_flow += flow[t];
    min_cost += dis[t] * flow[t];
}

int main () {
    memset(head, -1, sizeof(head));
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> b[i].x >> b[i].y;
    for (int i = 1; i <= n; ++ i) cin >> w[i].x >> w[i].y;

    s = 0, t = 2 * n + 1;
    for (int i = 1; i <= n; ++ i) {
        add_edge(s, i, 1, 0);
        add_edge(i + n, t, 1, 0);
    }
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            add_edge(i, j + n, 1, get_dis(w[i], b[j]));
    while (spfa() == true) update();
    for (int i = 1; i <= n; ++ i) {
        for (int j = head[i]; j != -1; j = e[j].next) {
            int to = e[j].to, c = e[j].c;
            if (c == 0) {
                res[to - n] = i;
                break;
            }
        }
    }
    for (int i = 1; i <= n; ++ i)
        cout << res[i] << endl;
    return 0;
}