二分图最大匹配(匈牙利算法) UVA 670 The dog task
2024-08-30 21:56:06
/*
题意:bob按照指定顺序行走,他的狗可以在他到达下一个点之前到一个景点并及时返回,问狗最多能走多少个景点
匈牙利算法:按照狗能否顺利到一个景点分为两个集合,套个模板
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std; const int MAXN = 1e2 + ;
const int INF = 0x3f3f3f3f;
struct P
{
int x, y;
double nxt;
}bob[MAXN], dog[MAXN];
double d[MAXN][MAXN];
bool vis[MAXN];
int lk[MAXN];
int lk2[MAXN];
vector<int> G[MAXN]; double get_dis(int x1, int y1, int x2, int y2)
{
return sqrt ((1.0) * ((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2)));
} bool DFS(int u)
{
for (int i=; i<G[u].size (); ++i)
{
int v = G[u][i];
if (!vis[v])
{
vis[v] = true;
if (lk[v] == - || DFS (lk[v]))
{
lk[v] = u; lk2[u] = v; return true;
}
}
} return false;
} void hungary(int n)
{
int res = ; memset (lk, -, sizeof (lk)); memset (lk2, -, sizeof (lk2));
for (int i=; i<n; ++i)
{
memset (vis, false, sizeof (vis));
if (DFS (i)) res++;
} printf ("%d\n", n + res);
for (int i=; i<n; ++i)
{
printf ("%d %d ", bob[i].x, bob[i].y);
if (lk2[i] != -) printf ("%d %d ", dog[lk2[i]].x, dog[lk2[i]].y);
}
printf ("%d %d\n", bob[n].x, bob[n].y);
} int main(void) //UVA 670 The dog task
{
// freopen ("UVA_670.in", "r", stdin); int t; scanf ("%d", &t);
while (t--)
{
int n, m; scanf ("%d%d", &n, &m);
for (int i=; i<=n; ++i)
{
scanf ("%d%d", &bob[i].x, &bob[i].y); G[i].clear ();
}
for (int i=; i<=m; ++i)
{
scanf ("%d%d", &dog[i].x, &dog[i].y);
} for (int i=; i<=n; ++i)
{
for (int j=; j<=m; ++j)
{
d[i][j] = get_dis (bob[i].x, bob[i].y, dog[j].x, dog[j].y);
}
} for (int i=; i<n; ++i)
{
bob[i].nxt = get_dis (bob[i].x, bob[i].y, bob[i+].x, bob[i+].y);
} for (int i=; i<n; ++i)
{
for (int j=; j<=m; ++j)
{
if (d[i][j] + d[i+][j] <= * bob[i].nxt) G[i].push_back (j);
}
} hungary (n);
if (t) puts ("");
} return ;
}
最新文章
- CI Weekly #7 | Instgram/Quora 等大公司如何做持续部署?
- iOS字体加载三种方式
- 享元模式/Flyweight模式/对象结构型/设计模式
- 规划SharePoint2010的管理员密码更改
- 运维自动化之ansible的安装与使用(包括模块与playbook使用)(转发)
- 2.C#自定义Attribute
- 分支语句:if
- 161123、ssh scp 复制文件和文件夹
- epoll的lt和et模式的实验
- Linux基础: 挂载镜像文件(Mount &; ISO)
- python学习笔记(win32print API介绍)
- Windows Embedded Compact 2013 安装体验
- 关于window.location不跳转的问题
- poj 3294 Life Forms(后缀数组)
- 配置Samba服务
- SmartBusinessDevFramework架构设计-3:考虑开源?
- 在windows下用C语言写socket通讯实例
- bind,apply,call区别总结
- Python编写的Linux邮件发送工具
- div高度随浏览器窗口高度变化;