已知如果两个星球属于同一个星系，那么他们之间的距离大于5光年，现在想知道最多有多少个星球可能属于银河系。 #include <iostream>
#include<vector>
#include<cstring>
#include<stdio.h>
using namespace std;
const int maxn = 55500 + 10;
vector<int>G[maxn];
int match[maxn];
bool used[maxn];
struct node
{
double x,y;
} s[maxn];
int n;
bool dfs(int v)
{
used[v]=true;
for(int i=0; i<G[v].size(); i++)
{
int u=G[v][i];
int w=match[u];
if(w<0||!used[w]&&dfs(w))
{
match[u]=v;
match[v]=u;
return true;
}
}
return false;
}
int matching()
{
int res=0;
memset(match,-1,sizeof(match));
for(int v=0; v<n; v++)
{
if(match[v]<0)
{
memset(used,0,sizeof(used));
if(dfs(v)) res++;
}
}
return res;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=0; i<n; i++) G[i].clear();
for(int i=0; i<n; i++)
{
scanf("%lf%lf",&s[i].x,&s[i].y);
}
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y)<=5*5))
{
G[i].push_back(j);
G[j].push_back(i);
}
}
}
printf("%d\n",n-matching());
}
return 0;
}
