codevs 2039 骑马修栅栏 USACO x
Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。
John是一个与其他农民一样懒的人。他讨厌骑马,因此从来不两次经过一个栅栏。你必须编一个程序,读入栅栏网络的描述,并计算出一条修栅栏的路径,使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马,在任意一个顶点结束。
每一个栅栏连接两个顶点,顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。两顶点间可能有多个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。
你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数,那么当存在多组解的情况下,输出500进制表示法中最小的一个 (也就是输出第一个数较小的,如果还有多组解,输出第二个数较小的,等等)。
输入数据保证至少有一个解。
第1行: 一个整数F(1 <= F <= 1024),表示栅栏的数目
第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。
输出应当有F+1行,每行一个整数,依次表示路径经过的顶点号。注意数据可能有多组解,但是只有上面题目要求的那一组解是认为正确的。
9
1 2
2 3
3 4
4 2
4 5
2 5
5 6
5 7
4 6
1
2
3
4
2
5
4
6
5
7
见描述
思路:
1.一笔画问题的升级版
2.搜索的时候一定要从有边的最小值开始
3.范围一定是到最大的数而不是到n
4.数据有相同的情况,所以不能简单的把map置1
5.输出格式!输出格式!输出格式!输出格式!输出格式!输出格式!输出格式!输出格式!输出格式!输出格式!输出格式!
坑点:
在用nows的时候,要先将初始化为1,然后再用然后再++,以此类推.如果不这样,会全WA
我真不知道为什么...
Eg:nows=0,用时ans[++nows]=now;会WAWAWAWAWA
然后如果nows=1,用时ans[nows]=now,nows++;会AC
(以下为6.24记)
编表的num从0开始++,跟从1开始++的区别
如果从0开始编号,在往上反的过程中会用到0(因为0的编号是0(为假)嘛),所以要将head数组手动设置为-1才能进入0号元素那条边,如果不设置为-,只能用1往后的边
所以
(Ps:now初始值为0)
void add(int pre,int to)
{
h[now].to=to;
h[now].next=heads[pre];
heads[pre]=now++;
/*
前提是heads数组已经设置为-1,并且在使用的时候
for(int j=heads[i];j!=-1;j=h[j].next)
或者
//for(int j=heads[i];~j;j=h[j].next)
~表示取反.
*/
}
而如果这样的话
void add(int pre,int to)
{
h[++now].to=to;
h[now].next=heads[pre];
heads[pre]=now;
/*
从一开始编号的话,到0就停止,所以不需要手动设置为-1
*/
}
(额...学姐说的%%%)
代码:
#include <iostream>
#include <cstdio>
#include <cmath> using namespace std; const int M = ;
int f,nows=,Ms;
int map[M][M],cishu[];
int ans[M]; void dfs(int now)
{
for(int i=;i<=Ms;i++)
{
if(map[now][i]>)
{
map[now][i]--;
map[i][now]--;
dfs(i);
}
}
ans[nows]=now;
nows++;
} int main()
{
scanf("%d",&f);
int x,y;
for(int i=;i<=f;i++)
{
scanf("%d%d",&x,&y);
map[x][y]++;
map[y][x]++;
cishu[x]++;
cishu[y]++;
Ms=max(Ms,max(x,y));
}
int flag=;
for(int i=;i<=Ms;i++)
{
if(cishu[i]%==)
{
flag=i;
break;
}
}
if(flag==)
{
for(int i=;i<=Ms;i++)
{
if(cishu[i]>)
flag=i;
break;
}
}
dfs(flag);
for(int i=nows-;i>=;i--)
cout<<ans[i]<<endl;
return ;
}
最新文章
- 掌握javascript中的最基础数据结构-----数组
- network issue troubleshooting
- 合法提交Html标签(2)
- 【BZOJ 3053】The Closest M Points
- hdu2795 线段树
- POJ 1611
- vs2010 配置OpenGL
- Swift 简单的通讯录
- logstash 处理tomcat日志
- 第五章SignalR的实时高频通讯
- 九九乘法表实现---基于python
- Centos6.7安装mysql 5.6简单教程
- [BZOJ3506] [Cqoi2014] 排序机械臂 (splay)
- linux下nginx负载均衡搭建
- 判断某个方法是否存在,解析php函数function_exists (),method_exists()与is_callable()的区别
- Eclipse 查看 WebService 服务请求和响应消息
- Java 实现文件压缩工具类
- .NET平台开源文档与报表处理组件包括Execel PDF Word等
- django 返回json数据
- 实现Java中的ArrayList
热门文章
- Cocos2d-X网络编程(4) Cocos2d中的网络通信协议——Socket通信
- Java课堂疑问解答与思考5
- MathType的配置问题;将word中的公式转换为mathtype格式失败,缺少OMML2MML.XSL
- 从零构建vue项目(一)--搭建node环境,拉取项目模板
- xmake新增对Qt编译环境支持
- linux rz上传-sz下载
- jenkins shell 取当前时间
- SQLSERVER 备份恢复之后提示缺少创建表权限的问题解决
- Windows Server 2012 上安装 dotNET Framework v3.5
- Python 入门之 闭包