P2526 [SHOI2001]小狗散步

原题链接：https://www.luogu.org/problem/P2526

其实这道题是一个非常水的题目，就是一个匈牙利算法…但是我一开始题目没看完，以为很难，瞄了一眼题解，发现是个二分图匹配，原来是我漏看了这句话：Pandog每次与主人相遇之前最多只去一个景点。

这就是一个妥妥的二分图最大匹配模板啊，我去，然后一下子就写完了….

这个代码我觉得非常快（可能是数据水



#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
inline int read() {
    char ch = getchar(); int x = 0, f = 1;
    while(ch < ‘0‘ || ch > ‘9‘) {
        if(ch == ‘-‘) f = -1;
        ch = getchar();
    } while(‘0‘ <= ch && ch <= ‘9‘) {
        x = x * 10 + ch - ‘0‘;
        ch = getchar();
    } return x * f;
} 
struct pos {
    double x;
    double y;
} datas [101];
pos pandog [101];
double dis (pos a,pos b) {
    return sqrt ((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int match [101];//pandog被哪个匹配了
int shit [101];    //datas与哪个匹配了 
int n,m;
bool fucked [101];
bool rmatch (int x) {
    for (int i = 1;i <= m;++ i) {
        //判断这个逼能不能被匹配
        if (dis (datas [x],pandog [i]) + dis (pandog [i],datas [x + 1]) > 2.0 * dis (datas [x],datas [x + 1]) ) {    //这个匹配不行 
            continue ;
        } 
        if (!fucked [i]) {
            //把这个傻逼腾出来
            fucked [i] = true ;
            if (!match [i] || rmatch (match [i])) {    //没匹配，或者可以赶走 
                match [i] = x;
                shit [x] = i;
                return true ;
            }
        }
    }
    return false ;
}
inline void xyl () {
    int ans = 0;
    for (int i = 1;i < n;++ i) {    //找一个地方滚过去 
        memset (fucked,false,sizeof fucked);
        if (rmatch (i)) {
            ++ ans;
        }
    }
    //开始计算答案
    cout << ans + n << endl;
    for (int i = 1;i <= n;++ i) {
        cout << datas [i].x << " " << datas [i].y << " ";
        if (shit [i]) {
            cout << pandog[shit [i]].x << " " << pandog[shit [i]].y << " ";
        }
    }
    cout << endl; 
}
int main() {
    n = read (),m = read ();
    for (int i = 1;i <= n;++ i) {
        cin >> datas [i].x >> datas [i].y;
    }
    for (int i = 1;i <= m;++ i) {
        cin >> pandog [i].x >> pandog [i].y;
    }
    //开始二分图匹配 匈牙利算法 
    xyl ();
    return 0;
}