[破碎的状态] [-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; }
Jan 27, 2024 05:37:20 PM
JNANABHUMI AP provides all latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources full information on each topic which can be accessed through Internet. To ensure that every readers get’s what important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who have passion to provide engaging content which is accurate, interesting and worthy to read. We are mope like a web community where you can find different information’s, resources, topics on day to day incidents or news. We provide you the finest of web content on each and every topics possible with help of editorial and content team.