当前位置:网站首页>P3033 [usaco11nov]cow steelchase g (similar to minimum path coverage)
P3033 [usaco11nov]cow steelchase g (similar to minimum path coverage)
2022-07-06 04:03:00 【Zhong Zhongzhong】
https://www.luogu.com.cn/problem/P3033
P3033 [USACO11NOV]Cow Steeplechase G
Cried and cried , I originally wanted to watch online classes , This inscription cost me a lot 2 hours .... Fortunately, it's a blue question , Or you'll lose a lot
Seriously summarize :
1. First 250250 Data over 10000 , Be sure to use the chained forward star method to save the map .
2. The difficulty of this problem lies in the establishment of graphics , Take the vertical line segment as the upper node , The lower node intersecting with it establishes a line segment ; The horizontal line serves as the lower node , Find the maximum matching tree , This is the minimum vertex covering
3.n- This value , The rest of the line segments have nothing to do with each other , That's the answer. .
4. The rest is the template of Hungarian algorithm *
#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++; // Number of vertical points
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;
}
边栏推荐
- Global and Chinese markets for otolaryngology devices 2022-2028: Research Report on technology, participants, trends, market size and share
- DM8 archive log file manual switching
- Global and Chinese markets for MRI safe implants 2022-2028: technology, participants, trends, market size and share Research Report
- Ks008 SSM based press release system
- SSTI template injection explanation and real problem practice
- [Key shake elimination] development of key shake elimination module based on FPGA
- Take you to wechat applet development in 3 minutes
- Le compte racine de la base de données MySQL ne peut pas se connecter à distance à la solution
- 简易博客系统
- Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
猜你喜欢
WPF effect Article 191 box selection listbox
Blue Bridge Cup - Castle formula
【leetcode】1189. Maximum number of "balloons"
Tips for using dm8huge table
Le compte racine de la base de données MySQL ne peut pas se connecter à distance à la solution
mysql关于自增长增长问题
C#(三十一)之自定义事件
An article will give you a comprehensive understanding of the internal and external components of "computer"
《2022年中国银行业RPA供应商实力矩阵分析》研究报告正式启动
MySql數據庫root賬戶無法遠程登陸解决辦法
随机推荐
asp. Core is compatible with both JWT authentication and cookies authentication
In Net 6 CS more concise method
Differential GPS RTK thousand search
Scalpel like analysis of JVM -- this article takes you to peek into the secrets of JVM
Exchange bottles (graph theory + thinking)
Thread sleep, thread sleep application scenarios
/usr/bin/gzip: 1: ELF: not found/usr/bin/gzip: 3: : not found/usr/bin/gzip: 4: Syntax error:
Esp32 (based on Arduino) connects the mqtt server of emqx to upload information and command control
mysql关于自增长增长问题
Codeforces Global Round 19
登录mysql输入密码时报错,ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: NO/YES
Global and Chinese markets for endoscopic drying storage cabinets 2022-2028: Research Report on technology, participants, trends, market size and share
判断当天是当月的第几周
Benefits of automated testing
C (thirty) C combobox listview TreeView
LTE CSFB test analysis
自动化测试怎么规范部署?
Maxay paper latex template description
Yyds dry goods inventory web components series (VII) -- life cycle of custom components
Simple blog system