欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

uva 670 The dog task

程序员文章站 2022-06-02 21:21:54
...

uva 670 The dog task
uva 670 The dog task

匈牙利算法,将狗的兴趣点与人走的每段路作二部图(即图的左边是点,右边是边),求出该二部图对于狗的兴趣点的最大匹配数,再加上人必经的点数,就是狗的路线。

#include <iostream>
#include <cmath>
#include <vector>
#include <cstring>
using namespace std;
const int Maxn=105;
int N,M;
double edge[Maxn];//存每条边的长度,即人走的每段路的长度
int match[Maxn];//记录每条边匹配的兴趣点
bool used[Maxn];//判断第i条边是否访问过
vector<int>graphy[Maxn];//邻接表储存二部图的连线
struct node
{
    double x,y;
}interesting[Maxn],Bob[Maxn];//分别存储狗的兴趣点和人必经的点
void initial()
{
    for(int i=0;i<Maxn;i++)
        graphy[i].clear();
}
double getDistance(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));//返回两点之间的距离
}
bool dfs(int u)
{
    for(int i=0;i<graphy[u].size();i++)// 循环第u个兴趣点可能匹配的所有边
    {
        int v=graphy[u][i];
        if(!used[v])
        {
            used[v]=true;
            if(match[v]==-1||dfs(match[v]))//若第v条边还未匹配或与第v条边匹配的兴趣点有其他匹配
            {
                match[v]=u;//将该边与兴趣点u匹配
                return true;//匹配成功
            }
        }
    }
    return false;
}
void MaxMatch()
{
    int res=0;
    memset(match,-1,sizeof(match));//将所有边的匹配初始化为 -1
    for(int i=1;i<=M;i++)
    {
        memset(used,false,sizeof(used));//每次匹配都将边的访问初始化为 false
        if(dfs(i))
            res++;
    }
    cout<<res+N<<endl;
    cout<<Bob[1].x<<" "<<Bob[1].y;
    for(int i=2;i<=N;i++)
    {
        if(match[i-1]!=-1)
        {
            int u=match[i-1];
            cout<<" "<<interesting[u].x<<" "<<interesting[u].y;
        }
        cout<<" "<<Bob[i].x<<" "<<Bob[i].y;
    }
    cout<<endl;
}
int main()
{
    int L;
    cin>>L;
    while(L--)
    {
        cin>>N>>M;
        initial();
        for(int i=1;i<=N;i++)
        {
            cin>>Bob[i].x>>Bob[i].y;//读取人必经的地点坐标
        }

        for(int i=1;i<N;i++)
        {

            edge[i]=getDistance(Bob[i].x,Bob[i].y,Bob[i+1].x,Bob[i+1].y);//记录人的路线的每条边的长度,共有k条边
        }
        for(int i=1;i<=M;i++)
        {
            cin>>interesting[i].x>>interesting[i].y;//读取狗可能经过的兴趣点
        }
        for(int i=1;i<=M;i++)//循环可能的兴趣点
        {
            for(int j=1;j<N;j++)//循环必须走的边(边数恰好为N-1)
            {
                if(edge[j]*2>=(getDistance(Bob[j].x, Bob[j].y,interesting[i].x,interesting[i].y)+getDistance(Bob[j+1].x, Bob[j+1].y, interesting[i].x,interesting[i].y)))
                    graphy[i].push_back(j);
            }
        }
        MaxMatch();
        if(L)
            cout<<endl;
    }
    return 0;
}