跳至正文

USACO 3.3-1 Riding the Fences骑马修栅栏

欧拉回路,我知道怎么做,但是我不知到为什么可以这么做!,囧囧;就当是背课文把,反正这就是欧拉回路。
如果有节点的度为奇数就从它开始,否则就从最小的开始,然后就是看下面的代码把:

 #include <stdio.h>
#define MAXV 500
#define MAXE 1024
char map[MAXV][MAXV];
int path[MAXE];
int degree[MAXV];
int len;
int max;

void add(int a, int b)
{
 map[a][b]++, degree[a]++;
}

void delete(int a, int b)
{
 map[a][b]--, degree[b]--;
}

int getneighbor(int a)
{
 int i;
 for(i = 0; degree[a] != 0; i++){
 if(map[i][a]){
 return i;
 }
 }
}

void fence(int now)
{
 int i;
 while(degree[now]){
 i = getneighbor(now);
 delete(i, now);
 delete(now, i);
 fence(i);
 }
 path[len++] = now;
}

int main(void)
{
 int i;
 int n, k = 501;
 int a, b;
 freopen(fence.in, r, stdin);
 freopen(fence.out, w, stdout);
 scanf(%d, &n);
 for(i = 0; i < n; i++){
 scanf(%d%d, &a, &b);
 a--, b--;
 add(a, b);
 add(b, a);
 if(max < a){
 max = a;
 }
 if(max < b){
 max = b;
 }
 if(k > a){
 k = a;
 }
 if(k > b){
 k = b;
 }
 }
 for(i = 0; i <= max; i++){
 if(degree[i] & 1){
 k = i;
 break;
 }
 }
 fence(k);
 for(i = len - 1; i >= 0; i--){
 printf(%d\\n, path[i] + 1);
 }
 return 0;
}

发表回复

您的电子邮箱地址不会被公开。