「poj 3565」 Ants (二分图完美匹配)

发表于 | 分类于 | | + s

poj 3565
题意：在坐标系中有$N$只蚂蚁，$N$棵苹果树，给你蚂蚁和苹果树的坐标。让每只蚂蚁去一棵苹果树，一棵苹果树对应一只蚂蚁。这样就有$N$条直线路线，问：怎样分配，才能使总路程和最小，且$N$条线不相交。

可以发现如果相交的两个线段一定可以修改为不相交(三角形)，且总路程和更小。题目保证有解，那么直接带权二分图完美匹配。这里可以费用流做，设源点$s$，汇点$t$，$s$到蚂蚁连边$(1,0)$($(cap, w)$表示容量和价值)，苹果树到$t$连边$(1, 0)$，每个蚂蚁到每个苹果树连边$(1, dist(a_i,b_j))$

最后在蚂蚁到苹果树边中容量为0的即为匹配边。

知识点：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int INF = 2147483647ll;
    const db eps = 1e-8;

    struct edge {
        int u, v, cap, nxt;
        db w;
    } ed[30000 + 5];
    struct node {
        int x, y;
    } nd[300 + 5];

    int n, s, t;
    int en, hd[300 + 5];
    int vis[300 + 5], incf[300 + 5], pre[300 + 5];
    db dis[300 + 5];

    db dist(int a, int b) {return sqrt((nd[a].x - nd[b].x) * (nd[a].x - nd[b].x) + (nd[a].y - nd[b].y) * (nd[a].y - nd[b].y));}
    void ins_c(int u, int v, int c, db w) {
        ed[++en] = (edge){u, v, c, hd[u], w}, hd[u] = en;
        ed[++en] = (edge){v, u, 0, hd[v], -w}, hd[v] = en;
    }

    queue<int > q;
    bool spfa() {
        for (int i = 0; i <= 2 * n + 2; ++i) vis[i] = 0, incf[i] = INF, dis[i] = INF, pre[i] = -1;
        vis[s] = 1, dis[s] = 0.0, q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            vis[u] = 0;
            for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
                edge &e = ed[i];
                if (fabs(dis[u] - INF) > eps && e.cap && dis[e.v] > dis[u] + e.w) {
                    dis[e.v] = dis[u] + e.w;
                    incf[e.v] = min(incf[u], e.cap);
                    pre[e.v] = i;
                    if (!vis[e.v]) vis[e.v] = 1, q.push(e.v);
                }
            }
        }
        return fabs(dis[t] - INF) > eps;
    }
    void update() {
        int now = pre[t];
        while (now != -1) {
            ed[now].cap -= incf[t], ed[now ^ 1].cap += incf[t];
            now = pre[ed[now].u];
        }
    }

    void clean() {
        en = -1, ms(hd, -1);
    }
    int solve() {

        clean();

        scanf("%d", &n), s = 2 * n + 1, t = 2 * n + 2;
        for (int i = 1; i <= 2 * n; ++i) scanf("%d%d", &nd[i].x, &nd[i].y);

        for (int i = 1; i <= n; ++i) ins_c(s, i, 1, 0.0), ins_c(i + n, t, 1, 0.0);

        for (int i = 1; i <= n; ++i) {
            for (int j = n + 1; j <= 2 * n; ++j) {
                ins_c(i, j, 1, dist(i, j));
            }
        }

        // 费用流 
        while (spfa()) update();

        for (int u = 1; u <= n; ++u) {
            for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
                edge &e = ed[i];
                if (n + 1 <= e.v && e.v <= 2 * n && e.cap == 0) {
                    printf("%d\n", e.v - n);
                    break ;
                } 
            }
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------