5、C++経典例題:馬に乗って柵を修理する
1698 ワード
5、馬に乗って柵を修理する
(時間制限:1000 msメモリ制限:65536 KB)
説明
農民のジョンは毎年多くの柵を修理しなければならない.彼はいつも馬に乗って柵を通り抜けて破損した場所を修復している.ジョンは怠け者で、馬に乗るのが嫌いなので、同じ柵を2回も通ったことがない.今、プログラムを作成して、フェンスネットワークの説明を読み込み、フェンスを修理する経路を計算して、フェンスごとにちょうど1回通過させます.Johnはいずれかの頂点(すなわち2つの柵の交点)から乗馬を開始し、いずれかの頂点で終了することができる.各フェンスには2つの頂点が接続されており、頂点は1~500の番号で接続されています(農場によっては500の頂点はありませんが).1つの頂点には、任意の複数(>=1)のフェンスを接続できます.すべての柵はつながっています(つまり、任意の柵から別のすべての柵に着くことができます).あなたのプログラムは馬に乗る経路(道を順番に通る頂点番号で表される)を出力しなければなりません.出力の経路を500進数と見なせば,複数組の解が存在する場合,500進数表現のうち最小の1つ(すなわち,出力1番目の小さい数,複数組の解がある場合,出力2番目の小さい数など)を出力する.入力データは、少なくとも1つの解を保証します.
入力
1行目:フェンスの数を表す整数F(1<=F<=1024).2行目からF+1行目:行ごとに2つの整数i,j(1<=i,j<=500)は、このフェンス接続iとj番頂点を表す.
しゅつりょく
出力にはF+1行が必要で、行ごとに整数が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
ソース:
(時間制限:1000 msメモリ制限:65536 KB)
説明
農民のジョンは毎年多くの柵を修理しなければならない.彼はいつも馬に乗って柵を通り抜けて破損した場所を修復している.ジョンは怠け者で、馬に乗るのが嫌いなので、同じ柵を2回も通ったことがない.今、プログラムを作成して、フェンスネットワークの説明を読み込み、フェンスを修理する経路を計算して、フェンスごとにちょうど1回通過させます.Johnはいずれかの頂点(すなわち2つの柵の交点)から乗馬を開始し、いずれかの頂点で終了することができる.各フェンスには2つの頂点が接続されており、頂点は1~500の番号で接続されています(農場によっては500の頂点はありませんが).1つの頂点には、任意の複数(>=1)のフェンスを接続できます.すべての柵はつながっています(つまり、任意の柵から別のすべての柵に着くことができます).あなたのプログラムは馬に乗る経路(道を順番に通る頂点番号で表される)を出力しなければなりません.出力の経路を500進数と見なせば,複数組の解が存在する場合,500進数表現のうち最小の1つ(すなわち,出力1番目の小さい数,複数組の解がある場合,出力2番目の小さい数など)を出力する.入力データは、少なくとも1つの解を保証します.
入力
1行目:フェンスの数を表す整数F(1<=F<=1024).2行目からF+1行目:行ごとに2つの整数i,j(1<=i,j<=500)は、このフェンス接続iとj番頂点を表す.
しゅつりょく
出力にはF+1行が必要で、行ごとに整数が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
ソース:
#include
#include
using namespace std;
int n,f;
int a[505][505];
int s[505],j[505],t,ma,o=505,k[505],q;//,l[505];
void bs(int x)
{
cout<0)
{
a[x][i]--;
a[i][x]--;
bs(i);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
cin>>f;
for(int i=1;i<=f;i++)
{
long long x,y;
scanf("%lld%lld",&x,&y);
if(k[x]==0)
{
k[x]=1;
q++;
}
if(k[y]==0)
{
k[y]=1;
q++;
}
a[x][y]++;
a[y][x]++;
s[y]++;
s[x]++;
if(x<=o)
o=x;
if(y<=o)
o=y;
}
for(int i=1;i<=f;i++)
if(s[i]%2==1)
{
t=i;
bs(i);
exit(0);
}
if(t==0)
bs(o);
return 0;
}