Watchcow
Time Limit: 3000MS
|
Memory Limit: 65536K
|
Total Submissions: 4550
|
Accepted: 1898
|
Special Judge
|
题目链接:http://poj.org/problem?id=2230
Description
Bessie's been appointed thenew watch-cow for the farm. Every night, it's her job to walk across the farmand make sure that no evildoers are doing any evil. She begins at the barn,makes her patrol, and then returns to the barn when she's done.
If she were a more observant cow, she might be able to just walk each of M (1<= M <= 50,000) bidirectional trails numbered 1..M between N (2 <= N<= 10,000) fields numbered 1..N on the farm once and be confident that she'sseen everything she needs to see. But
since she isn't, she wants to make sureshe walks down each trail exactly twice. It's also important that her two tripsalong each trail be in opposite directions, so that she doesn't miss the samething twice.
A pair of fields might be connected by more than one trail. Find a path thatBessie can follow which will meet her requirements. Such a path is guaranteedto exist.
Input
* Line 1: Two integers, N andM.
* Lines 2..M+1: Two integers denoting a pair of fields connected by a path.
Output
* Lines 1..2M+1: A list offields she passes through, one per line, beginning and ending with the barn atfield 1. If more than one solution is possible, output any solution.
Sample Input
4 5
1 2
1 4
2 3
2 4
3 4
Sample Output
1
2
3
4
2
1
4
3
2
4
1
Hint
OUTPUT DETAILS:
Bessie starts at 1 (barn), goes to 2, then 3, etc...
Source
USACO 2005 JanuarySilver
题意:
给你一张图,让你按不同顺序访问该图的所有边刚好2次。
解题思路:
这个题目用深搜就可以搞定,一般深搜是以点来判断是否已经搜索过,而这个是用边来判断,直到每条边都被搜索过,存储的时候应该是存储的无向图来当有向图,访问一条边就设置为访问过。
代码:
#include <iostream>
#include<cstdio>
#include<cstring>
#include <vector>
#define N 10003
using namespace std;
struct edge
{
int end;
int flag;
};
vector<edge> g[N];
int n ,m;
//递归深搜,遍历每一条边
void DFS(int s)
{
for(int i=0;i<g[s].size();i++)
{
if(g[s][i].flag==1)
{
g[s][i].flag=0;
DFS(g[s][i].end);
}
}
printf("%d\n",s);
}
int main()
{
scanf("%d%d",&n,&m);
int i;
int s,e;
memset(g,0,sizeof(g));
for(i=1;i<=m;i++)
{
scanf("%d%d",&s,&e);
edge temp;
temp.end=e;
temp.flag=1;
g[s].push_back(temp);
temp.end=s;
g[e].push_back(temp);
}
DFS(1);
return 0;
}
分享到:
相关推荐
2遍dp poj_3613解题报告 poj_3613解题报告
poj题目2775文件子目录源代码,递归经典题目,
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
O(nlogn)凸包问题 poj2187
POJ 3131 双向BFS解立体八数码问题
poj两道题的c++实现。已经测试过可以通过oj
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
poj 3310 的代码和方法说明,个人原创
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。
POJ上面题目的解题报告。涵盖挺多的。可作参考。代码都正确。ACM新手入门必下~~ 加油...
三道几何题:hdu 1007、hdu 2289、poj 3714