欧拉路小结 JZYZOJ1210 骑马修栅栏

现在写到欧拉路,理解起来并不算特别困难...吧...

但是非常恶心的是每次都要调试半天,做不到一遍两遍就能ac

每次写程序都对于程序的整体构架没有清晰的思路,想到哪里写到哪里真的是个非常差的习惯[尽管在写不出来的时候非常有用],所以快点改掉吧.

似乎也没有什么特别困难的部分,相关的题在oj上是p1209-p1211

数组一定要记得稍微开大一点,不要顺手就打一个数据范围上去,很初级也很常见的错误

应该深入理解一下dfs之后记录的作用,但是我到现在还不理解

以p1210为例

☆骑马修栅栏


	描述 Description
	农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过同一个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，在任意一个顶点结束。每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任意一个栅栏到达另外的所有栅栏)。你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小的，等等)。


	输入格式 Input Format
	第1行: 一个整数F(1 <= F <= 1024)，表示栅栏的数目第2到F+1行: 每行两个整数i, j(1 <= i,j <= 500)表示这条栅栏连接i与j号顶点。


	输出格式 Output Format
	输出应当有F+1行，每行一个整数，依次表示路径经过的顶点号。注意数据可能有多组解，但是只有上面题目要求的那一组解是认为正确的。


	样例输入 Sample Input


	样例输出 Sample Output


	时间限制 Time Limitation
	1s


	注释 Hint
	字典序最小的欧拉路给一个例子：


	来源 Source
	usaco 3.3.1

Flag	Accepted
题号	P1210
类型(?)	图结构
通过	58人
提交	205次
通过率	28%
难度	1

代码如下[里面有非常不必要的东西..但是都这样了也懒得改回去了]

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int maxn=;

 int tail=;

 int flag=;

 int f,ss;

 int sta[]={};

 int sum[]={};

 int woc[][]={};

 int mos[][]={};

 int cun[]={};

 void mydfs(int x,int k){

     for(int i=;i<=mos[x][];i++){

         int w=mos[x][i];

         if(woc[x][w]!=){

             woc[x][w]-=;

             woc[w][x]-=;

             mydfs(w,k+);

             cun[ss--]=w;//这个--肥肠重要,嗯我也不会解释,复习的时候看着理解好了

                     if(ss==){

                 for(int i=;i<=f+;i++){

                     cout<<cun[i]<<endl;

                 }

             }

         }

     }

 }

 int main(){

     cin>>f;

     ss=f+;

     for(int i=;i<=f;i++){

         int x,y;

         cin>>x>>y;

         if(x>maxn){

             maxn=x;

         }

         if(y>maxn){

             maxn=y;

         }

         sum[x]++;

         sum[y]++;

         mos[y][++mos[y][]]=x;

         mos[x][++mos[x][]]=y;

         woc[x][y]+=;

         woc[y][x]+=;

     }

     for(int i=;i<=maxn;i++){

         if(mos[i][]!=){

             sort((int*)mos+*i+,(int*)mos+*i+mos[i][]+);

         }

     }

     int f1=;

     for(int i=;i<=;i++){

         if(sum[i]%==){

             f1=i;

             break;

         }

     }

     if(f1!=){

         cout<<f1<<endl;

         mydfs(f1,);

     }

     else{

         cout<<<<endl;

         mydfs(,);

     }

     return ;

 }