POJ1486模拟或者匈牙利变种
题意:
有n个矩形,每个矩形上的某个位置上都有一个点,但是由于矩形是透明的,当一些矩形重叠在一起的时候就很可能分不清哪个点是那个矩形的,给你n个矩形的坐标,还有n个点的坐标,然后让你找出所有能确定的点。
思路:
两种方法做的,第一种是用的模拟的方法,我是这么想的,如果把一个状态给我们自己我们会怎么判断?我肯定是先找到我一眼就能看出来的删除,什么样的算是可以删除的?如果一个框上只有一个点,或者一个点只在一个框上,那么就可以肯定找到了一对,这样做的话要考虑到一个问题,那么就是有对是一看看不出来的,也就是说一开始断定不了,随着一些可以断定的删除之后就可以断定了,所以要while(1)循环的去找,这样显然是能搞定的,写的时候可以存两个方向的图,还有度数...模拟细节不啰嗦,然后就是第二种方法,这个方法比较容易写,也是大多数人认可的方法,但是一开始我并没有写,原因是我很难说服我自己这种方法是对的,因为我总担心,如果当前这条边不是匹配的关键边,但是随着别的边的删除,后来不是匹配的有成了匹配的怎么办?这么想可能是因为我写的第一种方法while(1)的原因,后来就是不停的自己画画画,终于明白了,哎!其实是我自己想多了,首先用匹配去做与我的第一种方法根本没有任何关联,也就是思路完全不同,匹配的思路就是只要是关键边,那么删除之后肯定是对匹配数有影响,如果没有影响的边,无论怎么while(1)最后还是没有影响,因为至少出现一组可以和他替换的边,这么这两组(或多组)可以互相替换的边彼此束缚着对方,就像是死锁一样,已经死锁的关联进程中,无论你以什么样的顺序去尝试执行都没意义,因为你“在环里了”,匹配的实现起来比较简单,直接匹配一遍,然后尝试删除匹配好的边就行了。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N_node 26 + 5
#define N_edge 26 * 26 + 10
using namespace std;
typedef struct
{
int to ,next;
}STAR;
typedef struct
{
int x1 ,x2 ,y1 ,y2;
}EDGE;
typedef struct
{
int x ,y;
}NODE;
typedef struct
{
int id;
char c;
}ANS;
ANS ans[N_node];
STAR E[N_edge];
EDGE edge[N_node];
NODE node[N_node];
int list[N_node] ,tot;
int mkdfs[N_node] ,mkgx[N_node];
int p1[N_node] ,p2[N_node];
void add(int a ,int b)
{
E[++tot].to = b;
E[tot].next = list[a];
list[a] = tot;
}
int DFS_XYL(int x ,int a ,int b)
{
for(int k = list[x] ;k ;k = E[k].next)
{
int to = E[k].to;
if(x == a && b == to)
continue;
if(mkdfs[to]) continue;
mkdfs[to] = 1;
if(mkgx[to] == -1 || DFS_XYL(mkgx[to] ,a ,b))
{
mkgx[to] = x;
return 1;
}
}
return 0;
}
int XYL(int n ,int a ,int b)
{
memset(mkgx ,255 ,sizeof(mkgx));
int ans = 0;
for(int i = 1 ;i <= n ;i ++)
{
memset(mkdfs ,0 ,sizeof(mkdfs));
ans += DFS_XYL(i ,a ,b);
}
return ans;
}
bool jude(EDGE a ,NODE b)
{
return a.x1 <= b.x && a.x2 >= b.x && a.y1 <= b.y && a.y2 >= b.y;
}
bool camp(ANS a ,ANS b)
{
return a.c < b.c;
}
int main ()
{
int n ,i ,j ,cas = 1;
while(~scanf("%d" ,&n) && n)
{
for(i = 1 ;i <= n ;i ++)
scanf("%d %d %d %d" ,&edge[i].x1 ,&edge[i].x2 ,&edge[i].y1 ,&edge[i].y2);
for(i = 1 ;i <= n ;i ++)
scanf("%d %d" ,&node[i].x ,&node[i].y);
memset(list ,0 ,sizeof(list));
tot = 1;
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
if(jude(edge[i] ,node[j]))
add(i ,j);
XYL(n ,0 ,0);
for(i = 1 ;i <= n ;i ++)
p1[i] = mkgx[i] ,p2[i] = i;
int ansid = 0;
for(i = 1 ;i <= n ;i ++)
{
if(XYL(n ,p1[i] ,p2[i]) != n)
{
ans[++ansid].c = p1[i] + 'A' - 1;
ans[ansid].id = p2[i];
}
}
printf("Heap %d\n" ,cas ++);
if(!ansid) printf("none\n");
else
{
sort(ans + 1 ,ans + ansid + 1 ,camp);
for(i = 1 ;i <= ansid ;i ++)
{
if(i == 1) printf("(%c,%d)" ,ans[i].c ,ans[i].id);
else printf(" (%c,%d)" ,ans[i].c ,ans[i].id);
}
printf("\n");
}
printf("\n");
}
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N_node 26 + 5
#define N_edge 26 * 26 + 10
using namespace std;
typedef struct
{
int to ,next;
}STAR;
typedef struct
{
int x1 ,y1 ,x2 ,y2;
}HDP;
typedef struct
{
int x ,y;
}NODE;
typedef struct
{
char c;
int id;
}ANS;
STAR E1[N_edge] ,E2[N_edge];
HDP hdp[N_node];
NODE node[N_node];
ANS ans[N_node];
int list1[N_node] ,list2[N_node] ,tot;
int dep1[N_node] ,mkuse1[N_node];
int dep2[N_node] ,mkuse2[N_node];
bool camp(ANS a ,ANS b)
{
return a.c < b.c;
}
void add(int a ,int b)
{
E1[++tot].to = b;
E1[tot].next = list1[a];
list1[a] = tot;
E2[tot].to = a;
E2[tot].next = list2[b];
list2[b] = tot;
}
bool jude(HDP a ,NODE b)
{
return a.x1 <= b.x && a.x2 >= b.x && a.y1 <= b.y && a.y2 >= b.y;
}
int main ()
{
int n ,i ,j ,cas = 1;
while(~scanf("%d" ,&n) && n)
{
for(i = 1 ;i <= n ;i ++)
scanf("%d %d %d %d" ,&hdp[i].x1 ,&hdp[i].x2 ,&hdp[i].y1 ,&hdp[i].y2);
for(i = 1 ;i <= n ;i ++)
scanf("%d %d" ,&node[i].x ,&node[i].y);
memset(list1 ,0 ,sizeof(list1));
memset(list2 ,0 ,sizeof(list2));
tot = 1;
memset(dep1 ,0 ,sizeof(dep1));
memset(dep2 ,0 ,sizeof(dep2));
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
if(jude(hdp[i] ,node[j]))
{
add(i ,j);
dep1[i] ++;
dep2[j] ++;
}
int ansid = 0;
memset(mkuse1 ,0 ,sizeof(mkuse1));
memset(mkuse2 ,0 ,sizeof(mkuse2));
while(1)
{
int mk = 0;
for(i = 1 ;i <= n ;i ++)
{
if(dep1[i] == 1 && !mkuse1[i])
{
mkuse1[i] = 1;
mk = 1;
int to;
for(int k = list1[i] ;k ;k = E1[k].next)
{
if(!mkuse2[E1[k].to])
{
mkuse2[E1[k].to] = 1;
to = E1[k].to;
break;
}
}
dep2[to] --;
for(int k = list2[to] ;k ;k = E2[k].next)
dep1[E2[k].to] --;
ans[++ansid].c = i + 'A' - 1;
ans[ansid].id = to;
}
}
for(i = 1 ;i <= n ;i ++)
{
if(dep2[i] == 1 && !mkuse2[i])
{
mkuse2[i] = 1;
mk = 1;
int to;
for(int k = list2[i] ;k ;k = E2[k].next)
{
if(!mkuse1[E2[k].to])
{
mkuse1[E2[k].to] = 1;
to = E2[k].to;
break;
}
}
dep1[to] --;
for(int k = list1[to] ;k ;k = E1[k].next)
dep2[E1[k].to] --;
ans[++ansid].c = to + 'A' - 1;
ans[ansid].id = i;
}
}
if(!mk) break;
}
printf("Heap %d\n" ,cas ++);
if(!ansid) printf("none\n");
else
{
sort(ans + 1 ,ans + ansid + 1 ,camp);
for(i = 1 ;i <= ansid ;i ++)
{
if(i == 1) printf("(%c,%d)" ,ans[i].c ,ans[i].id);
else printf(" (%c,%d)" ,ans[i].c ,ans[i].id);
}
printf("\n");
}
printf("\n");
}
return 0;
}
最新文章
- 【软件推荐】 Moom-窗口布局软件(V.3.2.2)【破解+汉化】
- mac下使用sencha cmd+extjs6
- UVa 1349 (二分图最小权完美匹配) Optimal Bus Route Design
- C# 判断两张图片是否一致的快速方法
- Android Studio使用远程依赖时下载不了jar包的解决方法
- 查看Linux声卡基本信息[转载]
- 使用SmsManager服务群发短信
- Instrument详解
- “最美天气”Python抓取天气
- WeTest----如何使用WeTest进行App性能测试?
- python学习笔记(五)
- AI 蒙特卡罗算法
- 一名网工对Linux运维的一次经历
- 微信小程序:bindtap等事件传参
- L2-008. 最长对称子串
- 本地IP,掩码,网关,DNS设置
- django 生成csv文件重要代码
- 使用Eclipse的JUnit实例
- C51学习笔记
- Django之logging日志使用
热门文章
- mysql内一些可以布尔盲注的查询语句
- 完全使用 VSCode 开发的心得和体会
- 【odoo14】第三章、创建插件
- salesforce零基础学习(一百零二)Limitation篇之 CPU Limit
- "; ";( 双引号) 与 &#39; &#39;( 单引号) 差在哪?-- Shell十三问<;第四问>;
- 解决wampserver 服务无法启动
- Golang+Protobuf+PixieJS 开发 Web 多人在线射击游戏(原创翻译)
- java面试-生产环境出现CPU占用过高,谈谈你的分析思路和定位
- windows上phpstudy配置memcache
- Spring Authorization Server 全新授权服务器整合使用