倒数第二个点目测是卡死循环了,九敏

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

BeMissJRsdog @ 2022-09-06 19:45:26

#include<bits/stdc++.h>
using namespace std;
int st=1,en=1,m,n,b[10001];
bool flag;
int rd[501];
int sum[501][501],mp[501][501],used[501][501];
inline void dfs(register int k,register int u){
    if(flag)return;
//  printf("%d\n",u);
    if(k==m+1){
        for(register int i=1;i<k;i++)printf("%d\n",b[i]);
        printf("%d",u);
        flag=1;
        return;
    }
    for(register int i=1;i<=n;i++){
        if(flag)return;
        if(used[u][i]>=sum[u][i])continue;
        if(!mp[u][i])continue;
        used[u][i]++;
        used[i][u]++;
        b[k]=u;
        dfs(k+1,i);
        used[u][i]--;
        used[i][u]--;
    }
}
int main(){
    scanf("%d",&m);
//  if(m==500){
//      
//  } 
    for(register int i=1;i<=m;i++){
        register int u,v;
        scanf("%d%d",&u,&v);
        n=max(n,max(u,v));
//      printf("%d %d\n",u,v);
        mp[u][v]=mp[v][u]=1;
        sum[u][v]++;
        sum[v][u]++;
        rd[u]++;
        rd[v]++; 
    }
//  for(register int i=1;i<=n;i++){
//      for(register int j=1;j<=n;j++){
//          cout<<mp[i][j]<<' ';
//      }
//      cout<<'\n';
//  }
    register int sum=0;
    for(register int i=1;i<=n;i++){
        if(rd[i]%2!=0){
            sum++;
            if(sum==1){
                st=i;
            }
            if(sum==2){
                en=i;
            }
        }
    }
    dfs(1,min(st,en));
    return 0;
}

https://wwz.lanzouy.com/iHKWv0b6iffg


by wenjingqi @ 2022-11-20 14:29:06

深搜要等找到正确路线再存储 比如数据

4

1 2

1 3

3 4

4 1

就会卡住,所以要在最后循环结束存储


|