Link:

P2526 传送门

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 ;
}

最新文章

  1. (转)SQLServer实例讲解
  2. 借用layer让弹层不限制在iframe内部
  3. PLSQL_性能优化系列18_Oracle Explain Plan解析计划通过Baseline绑定
  4. hive 桶相关特性分析
  5. ios日历视图实现日期输入
  6. java基本输入类型数据System.out.println()或System.out.print()
  7. sublime比较好用的插件
  8. 再回首UML之下篇
  9. Spring 完成自动注入(autowire)
  10. 产品经理教你如何构建电商电销 CRM 系统
  11. 黄聪:用 CSS 实现元素垂直居中,有哪些好的方案?
  12. delphi 主线程向子线程发送消息
  13. 【Unity】4.7 摄像机
  14. 三篇文章了解 TiDB 技术内幕 —— 谈调度
  15. Linux命令:查看文件内容cat|tac|more|less|head|tail|nl|od
  16. 防范xss的正确姿势
  17. 有关dubbo面试的那些事儿
  18. android how to deal with data when listview refresh
  19. AJAX如何获取从前台传递过来的数据然后在通过servle传递给后台
  20. sql where 1=1和 0=1 的作用(多条件查询错误的问题)

热门文章

  1. 关于auto-keras训练cnn模型
  2. windows7_常用操作终端操作
  3. 广度优先搜索--POJ迷宫问题
  4. printf格式化输出
  5. HDU 3480 Division(斜率DP裸题)
  6. HDU-1934
  7. How ConcurrentHashMap offers higher concurrency without compromising thread safety
  8. python 单例模式4中实现方法
  9. Zookeeper之Curator(1)客户端对节点的一些监控事件的api使用
  10. Go语言中的匿名函数和闭包的样子