[破碎的状态] [-4] POJ 2536
感谢@JCarlson带我找的题..
一个二分图的题,题意:
n个点,每个点要去匹配另一个点m
每个m只能匹配一个跟它距离不超过s*v的点
求最多有多少个点匹配不到
注意题意,是匹配不到
多测
...居然写错若干次..没救了呢
代码:
#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<string> #include<time.h> #include<math.h> #include<memory> #include<vector> #include<bitset> #include<fstream> #include<stdio.h> #include<utility> #include<sstream> #include<string.h> #include<iostream> #include<stdlib.h> #include<algorithm> using namespace std; struct edge { int y; edge * next; }; int top=0; edge * new_edge() { static edge a[100005]; return &a[top++]; } edge * li[105]; void insert_edge(int x,int y) { edge * t=new_edge(); t->y=y; t->next=li[x]; li[x]=t; } bool visit[105]; int pairs[105]; int dfs(int x) { if (visit[x]) return false; visit[x]=true; edge * t; for (t=li[x];t!=0;t=t->next) { if ((pairs[t->y]==-1)||(dfs(pairs[t->y]))) { pairs[t->y]=x; return true; } } return false; } double ax[105],ay[105]; double bx[105],by[105]; double dist(double x1,double y1,double x2,double y2) { return ((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } int main() { #ifdef absi2011 freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n,m,s,v; for (;scanf("%d%d%d%d",&n,&m,&s,&v)!=-1;) { int i; for (i=0;i<n;i++) { scanf("%lf%lf",&ax[i],&ay[i]); } int j; for (j=0;j<m;j++) { scanf("%lf%lf",&bx[j],&by[j]); } top=0; memset(li,0,sizeof(li)); for (i=0;i<n;i++) { for (j=0;j<m;j++) { if (dist(ax[i],ay[i],bx[j],by[j])<=s*s*v*v) insert_edge(i,j); } } int ans=n; memset(pairs,-1,sizeof(pairs)); for (i=0;i<n;i++) { memset(visit,0,sizeof(visit)); ans-=dfs(i); } printf("%d\n",ans); } return 0; }