USACO chapter 3 section 3 Riding The Fences



USER: tian tianbing [tbbd4261]
TASK: fenceLANG: C++ Compiling...Compile: OKExecuting...
Test 1: TEST OK [0.022 secs, 4016 KB] 
Test 2: TEST OK [0.000 secs, 4016 KB]
Test 3: TEST OK [0.022 secs, 4016 KB] 
Test 4: TEST OK [0.022 secs, 4016 KB]
Test 5: TEST OK [0.011 secs, 4016 KB] 
Test 6: TEST OK [0.011 secs, 4016 KB]
Test 7: TEST OK [0.000 secs, 4016 KB] 
Test 8: TEST OK [0.043 secs, 4016 KB]All tests OK. 
Your program ('fence') produced all correct answers! 
This is your submission #3 for this problem. Congratulations!

欧拉回路也可能是欧拉路径,用dfs,从小到大搜,要求是输出字典序小的.
刚开始是输出放在函数里面,这样后两组测试数据过不了,
/*
ID:tbbd4261
PROG:fence
LANG:C++
*/
#include<fstream>
using namespace std;
ifstream fin("fence.in");
ofstream fout("fence.out");
const int MAX=505;
int adj[MAX][MAX]={0},F,nmax=0;
int cnt[MAX]={0};
int print[1025*2+100]={0},len=0;
void dfs(int u)
{
    //fout<<u<<endl;
    for(int v=1; v<=nmax; v++)
            if(adj[u][v])
            {
                         adj[u][v]--;
                         adj[v][u]--;
                         dfs(v);
            }    
    len++;
    print[len]=u;
}
int main()
{
    fin>>F;
    int i,s,t;
    for( i=1,s,t; i<=F; i++)
     {
            fin>>s>>t;
            cnt[s]++;
            cnt[t]++;
            adj[s][t]++;
            adj[t][s]++;
            if(s>nmax)nmax=s;
            if(t>nmax)nmax=t;
     }
    
     s=0;
     for(i=1; i<=nmax; i++)
              if(cnt[i]){
                         if(s==0)s=i;
                         if(cnt[i]%2==1){ s=i; break;}
              }
    
     dfs(s);
     for(int j=len; j>=1; j--)
             fout<<print[j]<<endl;
    
    return 0;
}

posted on 2010-08-08 17:34 田兵 阅读(164) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年8月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(2)

随笔分类(65)

随笔档案(65)

文章档案(2)

ACM

搜索

积分与排名

最新随笔

最新评论

阅读排行榜