「Luogu 2219」「SHOI2001」小狗散步 (二分图最大匹配)

2219
题意：见上。

考虑错误的解法(没有考虑一个景点走一次)，即枚举主人的路线，然后枚举一个可行景点给狗走。
但是如果一个景点走一次，这个方法就是错误的，因为枚举的可行景点之前可能已经被走过了。

那么这样的话，意思是一个地方有多个选择，最多选一个，求所有地方选的最大值。

转化成图论，发现是个二分图，而这就是二分图最大匹配。输出方案就输出连边的方案即可。网络流做法即找有流量的地方

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#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 MAXN = 1000 + 5;
    int cnt, n, m, lk[MAXN], vis[MAXN];
    vector<int> G[MAXN];
    int x[MAXN], y[MAXN], tot, fl[MAXN];

    db dist(int i, int j) {
        return sqrt(1.0 * (x[i] - x[j]) * (x[i] - x[j]) + 1.0 * (y[i] - y[j]) * (y[i] - y[j]));
    }

    bool hungary(int u) {
        for (int i = 0; i < G[u].size(); i++) {//枚举每个右边的点匹配 
            int v = G[u][i];
            if (vis[v] != cnt) {//尝试修改过的节点就不需要遍历了
                vis[v] = cnt;
                if (!lk[v] || hungary(lk[v])) {
                    lk[v] = u;
                    return true;//成功匹配 
                }
            }
        }
        return false;
    }
    void clean() {
        for (int i = 0; i <= max(n, m); i++) vis[i] = lk[i] = 0, G[i].clear();
    }
    int solve() {

        cin >> n >> m;

        clean();

        for (int i = 1; i <= n + m; ++i) scanf("%d%d", &x[i], &y[i]);

        for (int i = 1; i < n; ++i) {
            db zr_d = dist(i, i + 1) * 2.0;
            for (int j = 1; j <= m; ++j) {
                db dog_d = dist(i, j + n) + dist(i + 1, j + n);
                if (dog_d <= zr_d) 
                    G[j + n].push_back(i);
            }
        }
        tot = 0;
        for (int i = 1; i <= m; ++i) {
            if (hungary(cnt = n + i)) ++tot;
        }

        printf("%d\n", tot + n);

        for (int i = 1; i <= n; ++i) {
            printf("%d %d ", x[i], y[i]);
            if (lk[i]) printf("%d %d ", x[lk[i]], y[lk[i]]);
        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
*/