P3033 [USACO11NOV]Cow Steeplechase G(类似最小路径覆盖)
路径 最小 覆盖 类似 Cow
2023-09-11 14:15:53 时间
https://www.luogu.com.cn/problem/P3033
P3033 [USACO11NOV]Cow Steeplechase G
哭了哭了,本来想看网课的,这个题花了我快2个小时了。。。。还好是个蓝题,不然亏大了
认真总结下:
1.首先250250数据过万,肯定要使用链式前向星的方式存图。
2.本题难点在于建立图形,把竖着的线段作为上结点,与之相交的下结点建立线段;横着的直线作为下结点,求最大匹配树,这是是最小顶点覆盖
3.n-这个值,剩下的线段就互相没有关系,就是答案。
4.剩下的就是匈牙利算法的模板啦*
#include <bits/stdc++.h>
#define y1 y11
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1e6+5;
int link[maxn],n,head[maxn],cnt;
int p[maxn],x1[maxn],y1[maxn],x2[maxn],y2[maxn],n1;
bool used[maxn];
struct node
{
int to,nxt;
}e[maxn];
void add_edge(int from,int to)
{
e[++cnt].to=to;
e[cnt].nxt=head[from];
head[from]=cnt;
}
bool dfs(int u)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(!used[v])
{
used[v]=1;
if(link[v]==-1||dfs(link[v]))
{
link[v]=u;
return 1;
}
}
}
return 0;
}
int hungary()
{
memset(link,-1,sizeof(link));
int ret=0;
for(int i=1;i<=n;i++)
{
if(p[i]==2)
continue;
memset(used,0,sizeof(used));
if(dfs(i))
ret++;
}
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
if(x1[i]>x2[i]) swap(x1[i],x2[i]);
if(y1[i]>y2[i]) swap(y1[i],y2[i]);
if(x1[i]==x2[i]) p[i]=1,n1++; //竖着的点的个数
else
p[i]=2;
}
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(p[i]==1&&p[j]==2)
{
if(x1[i]>=x1[j]&&x2[i]<=x2[j]&&y1[i]<=y1[j]&&y2[i]>=y2[j])
add_edge(i,n1+j);
}
else if(p[i]==2&&p[j]==1)
{
if(x1[i]<=x1[j]&&x2[i]>=x2[j]&&y1[i]>=y1[j]&&y2[i]<=y2[j])
add_edge(j,n1+i);
}
}
}
printf("%d\n",n-hungary());
return 0;
}
相关文章
- POJ1422 最小路径覆盖
- POJ2060最小路径覆盖
- POJ1548最小路径覆盖
- HDOJ 5294 Tricks Device 最短路(记录路径)+最小割
- 【网络流24题】最小路径覆盖问题(最大流)
- HDU 3861 The King’s Problem(强连通+二分图最小路径覆盖)
- 资源 之 4.4 Resource通配符路径(拾贰)
- 路径总和
- 基于prim算法的网络最小生成树生成得到路径规划
- 基于Qlearning的室内路径规划控制算法的matlab程序
- 图的最小生成树:Dijkstra迪杰斯特拉算法--源点到图中各节点的最短路径
- Allegro如何查看PCB上器件的库路径操作指导
- C#【文件操作篇】使用Path类、Environment类获取路径、文件名、扩展名
- 数学之美:两点之间最快的路径
- SpringBoot启动指定配置文件路径
- 最小路径和
- 最大匹配数,最小路径覆盖数,最大独立数,最小点覆盖数 定理总结
- Vue--路由的基本使用(组件之间的跳转)new VueRouter---配置path和子组件---跳转路径带#<a href="#/register">---显示区域用<router-view>
- [LeetCode]64. 最小路径和
- 动态规划-基础(斐波那契数、爬楼梯、使用最小花费爬楼梯、不同路径、不同路径II、整数拆分、不同的二叉搜索树)
- nginx 80 下的一个路径 到 8888
- 最短路径算法整理(二)
- [LeetCode] 1091. Shortest Path in Binary Matrix 二进制矩阵中的最短路径
- [LeetCode] 931. Minimum Falling Path Sum 下降路径最小和
- Python获取最小路径,查找元素在list中的坐标
- 极客DIY:制作一个可以面部、自主规划路径及语音识别的无人机