[P2526][SHOI2001]小狗散步
2024-08-25 01:20:35
Link:
Solution:
一道提示非常到位的题目
题面中强调了在两个路径相邻点间只能再去至多一个点,且每个点只计算一次贡献
于是明显可以将原题看作询问在两个不相交点集间最多能连几条边
接下来将合法边连上跑二分图匹配就好了
Tip:二分图匹配时分清$X,Y$集合以及$match$数组是哪个集合的匹配值
Code:
#include <bits/stdc++.h> using namespace std;
typedef pair<int,int> P;
#define X first
#define Y second
const int MAXN=;
P a[MAXN],b[MAXN];
vector<int> G[MAXN];
int n,m,mat[MAXN],vis[MAXN],idx=; int dfs(int x)
{
vis[x]=idx;
for(int i=;i<G[x].size();i++)
{
int v=G[x][i],m=mat[v];
if(m==-||vis[m]!=idx&&dfs(m))
{mat[v]=x;return ;}
}
return ;
} double dist(P a,P b)
{return sqrt((a.X-b.X)*(a.X-b.X)+(a.Y-b.Y)*(a.Y-b.Y));} int main()
{
memset(mat,-,sizeof(mat));
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d%d",&a[i].X,&a[i].Y);
for(int i=;i<=m;i++)
scanf("%d%d",&b[i].X,&b[i].Y);
for(int i=;i<=n;i++)
{
double d=dist(a[i],a[i-]);
for(int j=;j<=m;j++)
if(*d>=dist(a[i],b[j])+dist(a[i-],b[j]))
G[j].push_back(i);
} int res=;
for(int i=;i<=m;i++,idx++) res+=dfs(i);
printf("%d\n",res+n);
for(int i=;i<=n;i++)
{
if(mat[i]!=-)
printf("%d %d ",b[mat[i]].X,b[mat[i]].Y);
printf("%d %d ",a[i].X,a[i].Y);
}
return ;
}
最新文章
- (转)SQLServer实例讲解
- 借用layer让弹层不限制在iframe内部
- PLSQL_性能优化系列18_Oracle Explain Plan解析计划通过Baseline绑定
- hive 桶相关特性分析
- ios日历视图实现日期输入
- java基本输入类型数据System.out.println()或System.out.print()
- sublime比较好用的插件
- 再回首UML之下篇
- Spring 完成自动注入(autowire)
- 产品经理教你如何构建电商电销 CRM 系统
- 黄聪:用 CSS 实现元素垂直居中,有哪些好的方案?
- delphi 主线程向子线程发送消息
- 【Unity】4.7 摄像机
- 三篇文章了解 TiDB 技术内幕 —— 谈调度
- Linux命令:查看文件内容cat|tac|more|less|head|tail|nl|od
- 防范xss的正确姿势
- 有关dubbo面试的那些事儿
- android how to deal with data when listview refresh
- AJAX如何获取从前台传递过来的数据然后在通过servle传递给后台
- sql where 1=1和 0=1 的作用(多条件查询错误的问题)