题目大意:
给定n 给定n个机器的位置
要求任意两个机器间的距离至少为1.3米
求最多能选择多少个机器
至少为1.3米 说明若是位于上下左右一步的得放就不行
将机器编号 将不能同时存在的机器连边
此时求最多能选择多少个机器 就是图中的最大独立集
最大独立集 = 点数 - 最小边覆盖 = 点数 - 最大匹配
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define LL long long #define gcd(i,j) __gcd(i,j) #define mem(i,j) memset(i,j,sizeof(i)) #define inc(i,j,k) for(int i=j;i<=k;i++) #define dec(i,j,k) for(int i=j;i>=k;i--) const int N=2e3+5; int n, x[N], y[N]; bool near(int i,int j) { if(abs(x[i]-x[j])+abs(y[i]-y[j])==1) return 1; return 0; } vector<int>G[N]; int match[N]; bool vis[N]; void addE(int i,int j) { G[i].push_back(j); G[j].push_back(i); } bool DFS(int u) { vis[u]=1; int len=G[u].size()-1; inc(i,0,len) { int v=G[u][i], w=match[v]; if(w==0 || !vis[w]&&DFS(w)) { match[u]=v, match[v]=u; //printf("mat %d %d\n",u,v); return 1; } } return 0; } int Match() { int res=0; mem(match,0); inc(i,1,n) if(!match[i]) { mem(vis,0); if(DFS(i)) res++; } //printf("%d\n",res); return res; } int main() { while(~scanf("%d",&n)) { inc(i,1,n) G[i].clear(); inc(i,1,n) scanf("%d%d",&x[i],&y[i]); inc(i,1,n) inc(j,1,n) if(i!=j && near(i,j)) addE(i,j); printf("%d\n",n-Match()); } return 0; }View Code