博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【AtCoder Regular Contest 092】C.2D Plane 2N Points【匈牙利算法】
阅读量:5736 次
发布时间:2019-06-18

本文共 970 字,大约阅读时间需要 3 分钟。

题意:给定N个红点二维坐标N个蓝点二维坐标,如果红点横纵坐标都比蓝点小,那么它们能够构成一组。问最多能构成多少组。

题解:把满足要求的红蓝点连线,然后就是匈牙利算法(详情见,写的好棒!)

1 #include
2 #include
3 #include
4 #include
5 using namespace std; 6 const int maxn=160; 7 int a[maxn],b[maxn],c[maxn],d[maxn]; 8 bool used[maxn]; 9 int girl[maxn],line[maxn][maxn];10 int n;11 12 bool Find(int x)13 {14 for(int j=1;j<=n;j++)15 {16 if(line[x][j]&&!used[j]){17 used[j]=1;18 if(girl[j]==0||Find(girl[j])){19 girl[j]=x;20 return true;21 }22 }23 }24 return false;25 }26 27 int main()28 {29 cin>>n;30 for(int i=1;i<=n;i++) cin>>a[i]>>b[i];31 for(int i=1;i<=n;i++) cin>>c[i]>>d[i];32 memset(line,0,sizeof(line));33 for(int i=1;i<=n;i++)34 {35 for(int j=1;j<=n;j++){36 if((a[i]

 

转载于:https://www.cnblogs.com/zxhyxiao/p/8596925.html

你可能感兴趣的文章
Nginx反向代理1--基本介绍-虚拟主机
查看>>
${pageContext.request.contextPath}
查看>>
java中循环的不同终止方式
查看>>
【测试基础】为人所知的那些事
查看>>
webpack4 系列教程(十二):处理第三方JavaScript库
查看>>
第一部分 Python如何运行
查看>>
图片嵌入-大容量的信息隐藏算法
查看>>
NAND flash和NOR flash的区别详解
查看>>
《小学生之噩梦》 用户规格说明书
查看>>
kaldi特征处理
查看>>
Android 防止控件被重复点击
查看>>
POJ3077 Rounders
查看>>
uva 712 S-Trees
查看>>
<botton>与<input type="button">的区别
查看>>
A Tour of Go Exercise: HTTP Handlers
查看>>
【alpha阶段】第八次Scrum Meeting
查看>>
iOS 判断输入是否全是空格
查看>>
认证客户端的链接与socketserver实现并发
查看>>
为什么选择.NETCore?
查看>>
15总结。(转)
查看>>