SHOI2001 小狗散步

题目传送门

感觉这题最大的难点是发现它的解法是二分图最大匹配

---

主人的路线是固定的，对于每一段的路线，我们可以枚举小狗想去的景点，如果时间够，我们就将这段路线的起点和小狗想去的点连起来

这样就形成了一个二分图，因为dog每次与主人相遇之前最多只去一个景点，所以这道题就转化成了二分图最大匹配

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
      k = k * 10 + c - 48, c = getchar();
    return k * f;
}
double X1[110], Y1[110], X2[110], Y2[110];
double calc(double a, double b, double c, double d) {
    return sqrt((c-a) * (c-a) + (d-b) * (d-b));
}
struct zzz {
    int t, nex;
}e[10010 << 1]; int head[110], tot;
void add(int x, int y) {
    e[++tot].t = y;
    e[tot].nex = head[x];
    head[x] = tot;
}
int lin[110], ans; bool vis[110];
bool find(int x) {
    for(int i = head[x]; i; i = e[i].nex) {
        if(!vis[e[i].t]) {
            vis[e[i].t] = 1;
            if(!lin[e[i].t] || find(lin[e[i].t])) return lin[e[i].t] = x, 1;
        }
    }
    return 0;
}
int step[110];
int main() {
    int n = read(), m = read();
    for(int i = 1; i <= n; ++i) X1[i] = read(), Y1[i] = read();
    for(int i = 1; i <= m; ++i) X2[i] = read(), Y2[i] = read();
    for(int i = 1; i <= n-1; ++i) {
        double x = calc(X1[i], Y1[i], X1[i+1], Y1[i+1]);
        for(int j = 1; j <= m; ++j) {
            if((calc(X1[i], Y1[i], X2[j], Y2[j]) + calc(X2[j], Y2[j], X1[i+1], Y1[i+1])) <= x * 2)
                add(i, j);
        }
    }
    for(int i = 1; i < n; ++i) {
        memset(vis, 0, sizeof(vis));
        ans += find(i);
    }
    printf("%d
", ans+n);
    for(int i = 1; i <= m; ++i) step[lin[i]] = i;
    for(int i = 1; i <= n; ++i) {
        printf("%.0lf %.0lf ", X1[i], Y1[i]);
        if(step[i]) 
            printf("%.0lf %.0lf ", X2[step[i]], Y2[step[i]]);
    }
    return 0;
}