SHOI2001 小狗散步

wjh15101051's space

卧薪尝胆，厚积薄发。

SHOI2001 小狗散步

Date: Fri Jul 20 19:29:00 CST 2018

In Category: NoCategory

Description：

一个人沿着固定的路径走，给出路径上点的坐标，一条狗想尽可能多的经过另外一些点，但必须在人的路径上的点依次与人会合，问狗最多能经过几个点。

$1\le n \le 100$

Solution：

将两点之间的路径看成左部点，另外的点看成右部点，如果狗在这段路径上能到达另一个点，就连边，求最大匹配即可。

Code：


#include

#include

#include

#include

#include

#include

using namespace std;

int n,m;

#define MAXN 110

double xa[MAXN],ya[MAXN];

double xb[MAXN],yb[MAXN];

struct edge

{

    int to,nxt;

}e[MAXN * MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    return;

}

int v[MAXN],cnt = 0;

int match[MAXN];

bool find(int k)

{

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(v[e[i].to] != cnt)

        {

            v[e[i].to] = cnt;

            if(match[e[i].to] == -1 || find(match[e[i].to]))

            {

                match[e[i].to] = k;

                return true;

            }

        }

    }

    return false;

}

int res[MAXN];

double dis(double a1,double b1,double a2,double b2)

{

    return sqrt((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2));

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i = 1;i <= n;++i)

    {

        scanf("%lf%lf",&xa[i],&ya[i]);

    }

    for(int i = 1;i <= m;++i)

    {

        scanf("%lf%lf",&xb[i],&yb[i]);

    }

    for(int i = 1;i < n;++i)

    {

        for(int j = 1;j <= m;++j)

        {

            if(dis(xa[i],ya[i],xb[j],yb[j]) + dis(xa[i + 1],ya[i + 1],xb[j],yb[j]) <= 2 * dis(xa[i],ya[i],xa[i + 1],ya[i + 1]))

            {

                add(i,j);

            }

        }

    }

    int ans = 0;

    cnt = 0;

    memset(match,-1,sizeof(match));

    for(int i = 1;i < n;++i)

    {

        ++cnt;

        if(find(i))++ans;

    }

    cout << ans + n << endl;

    for(int i = 1;i <= m;++i)

    {

        res[match[i]] = i;

    }

    for(int i = 1;i < n;++i)

    {

        cout << xa[i] << " " << ya[i] << " ";

        if(res[i] != 0)cout << xb[res[i]] << " " << yb[res[i]] << " ";

    }

    cout << xa[n] << " " << ya[n] << endl;

    return 0;

}

In tag: 图论-匈牙利算法

wjh15101051