TLE。。。

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

求败 @ 2017-06-26 17:19:50

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

int a[1000],s[1000][1000],du[2000],b[2000],c[1000],

    ii=0,flag=1,n=0,nn=100000000,m,l,r,ans=0,tot=0;
void dfs(int x){
    if(tot==m+1){
        flag=0;
        return;
    }
    for(int i=1;i<=ans;i++)
        if(s[x][c[i]]!=0){
            s[x][c[i]]--;
            s[c[i]][x]--;
            b[++tot]=c[i];
            dfs(c[i]);
            if(!flag)break;
            tot--;
            s[x][c[i]]++;
            s[c[i]][x]++;
        }
    return;
}
int main(){
    memset(a,0,sizeof(a));
    memset(s,0,sizeof(s));
    memset(du,0,sizeof(du));
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        a[l]++;
        a[r]++;
        n=max(n,l);
        n=max(n,r);
        nn=min(nn,l);
        nn=min(nn,r);
        s[l][r]++;
        s[r][l]++;
        du[l]++;
        du[r]++;
    }
    ans=0;
    for(int i=nn;i<=n;i++)
        if(a[i]!=0)
            c[++ans]=i;
    tot=0;
    for(int i=1;i<=ans;i++)
        if(du[c[i]]%2!=0){
            ii=c[i];
            break;
        }
    if(!ii){
        b[++tot]=nn;
        dfs(nn);
        for(int i=1;i<=m+1;i++)
            printf("%d\n",b[i]);
    }
    else{
        b[++tot]=ii;
        dfs(ii);
        for(int i=1;i》m+11;i++)
            printf("%d\n",b[i]);
    }
    return 0;
}

|