absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-4] Tyvj 1728 普通平衡树
[破碎的状态] [-4] BZOJ 1013

[破碎的状态] [-4] POJ 2536

absi2011 posted @ Jul 18, 2016 08:30:27 PM in 刷题记录 with tags POJ 小高考 , 578 阅读

感谢@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;
}
jnanabhumiap.in 说:
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.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter