kattis Programming Tutors 给游客与导游匹配(二分+二分图)

题目来源:https://vjudge.net/problem/Kattis-programmingtutors

题意:

有n个游客,n个导游,给出他们的坐标,问你怎么匹配可以使他们最大距离最小

题解:

用一个lim变量表示最远可以连接的距离,用二分图匹配,如果可以匹配则这个lim一定符合条件,用二分寻找最小的lim

好题

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100+5;
struct Node
{
int x,y;
}st[maxn],tu[maxn];
int n,match[maxn];
long long lim;
bool used[maxn]; inline int dis(Node a,Node b)
{
return abs(a.x-b.x)+abs(a.y-b.y);
}
int dfs(int x)
{ for(int i=1;i<=n;i++)
{
if(used[i]==0&&dis(st[x],tu[i])<=lim)
{
used[i]=1;
if(match[i]==0||dfs(match[i]))
{
match[i]=x;
return 1;
}
}
}
return 0; }
bool guar()
{
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++)
{
memset(used,0,sizeof(used));
if(dfs(i)==0)return 0;
}
return 1;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %d",&st[i].x,&st[i].y);
for(int i=1;i<=n;i++)
scanf("%d %d",&tu[i].x,&tu[i].y);
long long a=0,b=1e10;
while(a!=b)
{
long long mid=(a+b)/2;
lim=mid;
if(guar())
b=mid;
else
a=mid+1;
}
printf("%lld\n",a);
return 0;
}

  

上一篇:15个前卫的 HTML5 & CSS3 网页设计作品


下一篇:pycharm 注册码