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 小高考 , 545 阅读

感谢@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;
}

登录 *


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