补题：HUN暑期训练第三场-Programming Tutors（二分查找+最大匹配）

Dear 丶 2022-05-16 02:57 105阅读 0赞

题目链接：  
[Programming Tutors][]

题目大意：  
给你n个学生和n个教练的平面坐标，分别给学生分配教练，使得学生和教练最大距离最小，输出这个最大距离最小值

解题思路：  
第一次正式接触二分查找（满足单调性的题）的思想，真的好用！！！  
我们可以二分答案，然后使用匈牙利算法求出最大匹配，如果全部匹配，则r=mid;  
否则 l=mid+1

最后就是正确答案了

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <algorithm>
    #include <vector>
    
    using namespace std;
    
    #define ll long long
    
    struct point{
        ll x,y;
    }s[205], t[205];
    
    ll g[205][205],mid;
    int n;
    
    int link[105],vis[105];
    
    bool find(int u){
        for(int v=1; v<=n; ++v){
            if(g[u][v]<=mid&&!vis[v]){
                vis[v] = 1;
                if(link[v]==-1 || find(link[v])){
                    link[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    int check(){
        int ret = 0;
        for(int i=1; i<=n; ++i){
            memset(vis, 0, sizeof(vis));
            if(find(i)) ret++; 
        }
        return ret;
    }
    int main(){
    
        scanf("%d",&n);
        for(int i=1; i<=n; ++i){
            ll x,y;
            scanf("%lld%lld",&x,&y);
            s[i].x=x; s[i].y=y;
        }
        for(int i=1; i<=n; ++i){
            ll x,y;
            scanf("%lld%lld",&x,&y);
            t[i].x=x; t[i].y=y;
        }
    
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=n; ++j){
                g[i][j] = abs(s[i].x-t[j].x) + abs(s[i].y-t[j].y);
            }
        }
        ll l =0 , r=1e12;
        while(l<r){
            memset(link, -1, sizeof(link));
            mid = (l+r)/2;
            if(check()==n) r = mid;
            else l = mid+1;
        }
        printf("%lld\n",l);
        return 0;
    }

[Programming Tutors]: https://vjudge.net/problem/Kattis-programmingtutors