当前位置:网站首页>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;
}
边栏推荐
- Indicator system of KQI and KPI
- Record an excel xxE vulnerability
- Ipv4中的A 、B、C类网络及子网掩码
- Facebook等大厂超十亿用户数据遭泄露,早该关注DID了
- C#(二十九)之C#listBox checkedlistbox imagelist
- Thread sleep, thread sleep application scenarios
- Quick sort function in C language -- qsort
- 51nod 1130 n factorial length V2 (Stirling approximation)
- cookie,session,Token 这些你都知道吗?
- Class A, B, C networks and subnet masks in IPv4
猜你喜欢
[PSO] Based on PSO particle swarm optimization, matlab simulation of the calculation of the lowest transportation cost of goods at material points, including transportation costs, agent conversion cos
Web components series (VII) -- life cycle of custom components
Ks003 mall system based on JSP and Servlet
C mouse event and keyboard event of C (XXVIII)
An article will give you a comprehensive understanding of the internal and external components of "computer"
Factors affecting user perception
在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
Serial port-rs232-rs485-ttl
JVM的手术刀式剖析——一文带你窥探JVM的秘密
《2022年中国银行业RPA供应商实力矩阵分析》研究报告正式启动
随机推荐
Global and Chinese markets for patent hole oval devices 2022-2028: Research Report on technology, participants, trends, market size and share
Solution to the problem that the root account of MySQL database cannot be logged in remotely
Leetcode32 longest valid bracket (dynamic programming difficult problem)
Global and Chinese market of aircraft anti icing and rain protection systems 2022-2028: Research Report on technology, participants, trends, market size and share
Ks008 SSM based press release system
SSTI template injection explanation and real problem practice
Mapping between QoE and KQI
【PSO】基于PSO粒子群优化的物料点货物运输成本最低值计算matlab仿真,包括运输费用、代理人转换费用、运输方式转化费用和时间惩罚费用
[FPGA tutorial case 12] design and implementation of complex multiplier based on vivado core
Record an excel xxE vulnerability
DM8 backup set deletion
cookie,session,Token 这些你都知道吗?
登录mysql输入密码时报错,ERROR 1045 (28000): Access denied for user ‘root‘@‘localhost‘ (using password: NO/YES
MySQL transaction isolation level
MySql数据库root账户无法远程登陆解决办法
How can programmers resist the "three poisons" of "greed, anger and ignorance"?
Use js to complete an LRU cache
[introduction to Django] 11 web page associated MySQL single field table (add, modify, delete)
[meisai] meisai thesis reference template
Yyds dry goods inventory hcie security Day11: preliminary study of firewall dual machine hot standby and vgmp concepts