UVA663 Sorting Slides(烦人的幻灯片)
2024-10-02 05:31:09
UVA663 Sorting Slides(烦人的幻灯片)
第一次做到这么玄学的题,在《信息学奥赛一本通》拓扑排序一章找到这个习题(却发现标程都是错的),结果用二分图匹配做了出来
蒟蒻感觉思路不太好想,难度大概在蓝题~紫题。。
那是因为UVa输出换行空格万年老坑
#include<cstdio>
#include<cstring>
using namespace std;
#define N 27
int vis[N],match[N],ans[N],x1[N],x2[N],y1[N],y2[N],n,T;
bool g[N][N],flag;
inline bool dfs(int x) {
for (register int i=1; i<=n; i++)
if (!vis[i] && g[x][i]) {
vis[i]=1;
if (!ans[i] || dfs(ans[i])) {
ans[i]=x;//第 i 个幻灯片对应数字为 x
return true;
}
}
return false;
}
inline int find() {//求二分图最大匹配
int sum=0;
memset(ans,0,sizeof ans);
for (register int x=1; x<=n; x++){
memset(vis,0,sizeof vis);
if (dfs(x)) sum++;// 总匹配数
}
return sum;
}
int main() {
while(~scanf("%d",&n) && n) {
if (T) puts("");
printf("Heap %d\n",++T);
memset(g,0,sizeof g);
for (int i=1; i<=n; i++)
scanf("%d%d%d%d",&x1[i],&x2[i],&y1[i],&y2[i]);
for (int i=1,x,y; i<=n; i++) {
scanf("%d%d",&x,&y);
for (int j=1; j<=n; j++)
if (x>=x1[j] && x<=x2[j] && y>=y1[j] && y<=y2[j])
g[i][j]=1;//如果数字在幻灯片范围之内的话则连边,有机会匹配
}
int tot=find(),flag=0;
自此已求出当前的匹配,但程序还未结束,如果在此输出答案:
for (int i=1;i<=n;i++) printf("(%c,%d)",i-1+'A',ans[i]);
按照样例数据,你会发现第一组数据已有正确答案,而第二组数据不是none,而输出了匹配情况
这是因为题目还有一个要求:
若出现多种对应的情况,我们称这种对应是无法实现的。
第二组数据中A和B都可以匹配1和2中任意一个,所以对应不唯一
//接下来我们要去除这种情况
for (int j=1; j<=n; j++)
for (int i=1;i<=n; i++)
if (g[i][j]) {
g[i][j]=0;//考虑依次删去每条边,如果有唯一对应,那么至少有一边删去后使匹配数减少
if (find()!=tot) {
if (flag) printf(" ");
else flag=1;
printf("(%c,%d)",j-1+'A',i);//如果幻灯片 j 与 数字 i 是唯一搭配,直接输出
}
g[i][j]=1;
}
if (!flag) printf("none");//如果删去任意一边匹配数都不变,则对应不唯一
puts("");//相当于printf("\n");
}
return 0;
}
最新文章
- angular2系列教程(一)hello world
- Js权限判断处理
- 谈谈Fragment中的onActivityResult
- μC/OS-Ⅲ系统的任务切换和任务调度
- iOS开发中的错误整理,Changing the delegate of a tab bar managed by a tab bar controller is not allowed
- IL指令大全
- Solve error: Cannot open include file: &#39;X11/Xlocale.h&#39;: No such file or directory
- oracle server配置:监听程序未启动或数据库服务未注册到该监听程序
- Cannot find module formidable
- 文本框Edit
- Java 标准DBUtil 写法
- 芝麻HTTP:Python爬虫实战之抓取爱问知识人问题并保存至数据库
- nginx的配置与应用
- 更优雅地关闭资源 - try-with-resource及其异常抑制
- Paypal Rest Api自定义物流地址(跳过填写物流地址)
- JTable的模型
- Axure RP 快速原型设计工具
- 线程相关函数(3)-pthread_detach()将某个线程设成分离态
- react设置默认state和默认props
- ES6的let和const命令
热门文章
- UWP 设置控件样式四种方法
- tf.nn.softmax &; tf.nn.reduce_sum &; tf.nn.softmax_cross_entropy_with_logits
- QML学习【一】Basic Types
- QT信号槽的六个优点(虽然直接调用函数也可解决问题,但要在具体的函数中传递指针,多对一和解除关系也够麻烦的)
- Qt的QWaitCondition(允许线程在一定条件下唤醒其他线程,这样对不间断上传可能比较适用)
- GO方法与接口
- 爬取虎扑NBA首页主干道推荐贴的一只小爬虫,日常爬不冷笑话解闷
- RequestMappingHandlerAdapter和RequestParam原理分析
- Django 的路由系统
- 视频直播技术之iOS端推流