ACM: 117 - The Postal Worker Rings Once

這一題是給許多條「街道」，找出將每條街至少走過一次，並回到原點的最短路徑，傳回路徑總長。可以視作一個graph，找出將每個邊至少走一次，並回到原點的最小路徑權重值。這題有以下背景知識：

Eulerian Circuit/Eulerian Path (尤拉路徑)

題目有兩個要點，將這題指向尤拉路徑:
1. In each postal route there will be a path between all intersections, i.e., the intersections are connected. (所有的道路可以接通，即是這是一個連通圖)
2. There will be at most two intersections with odd degree. All other intersections will have even degree, i.e., an even number of streets meeting at that intersection. (圖裡最多只有兩個點會有奇數個邊，其他點都會有偶數個邊)

Eulerian Circuit是判斷一個圖(無向圖)存不存在一個路徑，能從一點開始不經過重複的邊走完全圖，再回到原點。存在的條件如下:
圖形上每一個端點(vertex)皆有偶數個邊(degree為偶數)
因為若有一個端點有奇數個邊，勢必有一條路只能去不能回。

Eulerian Path(Eulerian Chain)則是一筆劃問題，找圖上是否存在一個路徑，從一點開始不經過重複的邊走完全圖，但不一定要回到原點。存在的條件如下:
圖形上最多只有兩個端點有奇數個邊，其餘端點皆有偶數個邊
而在有端點為奇數degree的情況下，Eulerian Path必定從奇數degree的端點開始，並且結束於奇數degree的端點。因為拿掉造成奇數degree的邊，圖形就可以回到原點，因此Eulerian Path可以想成是先走完一圈回到原點，再去特別走「多出來」的路徑，所以一定開始結束在奇數degree的端點。

因此這題是Eulerian Path的問題，當所有端點的degree皆為偶數時，最短路徑即是所有路徑的總和；而因為需要回到原點，當有奇數degree端點存在時，需再找出奇數degree端點之間的最小路徑，以回到原點。

 

Handshaking Lemma (握手定裡)

題目寫了"There will be at most two intersections with odd degree"，是「最多」兩個端點有奇數degree，但只有一個端點有奇數degree的情況是否可能存在呢？

從handshaking lemma可以了解這個情況是不可能的，因為好比兩人握手的時候，必然是兩個人都伸出手來，因此一個端點有奇數個邊，也必然有相應的點去連接那個邊，雙向計算的結果是，任何一個(無向)圖，擁有奇數個邊的端點數是偶數！

因此這個題目只有兩種情況：全部端點皆有偶數個邊，或只有兩個端點有奇數個邊。

 

寫出來Runtime 0.008，這題平均runtime超短的，要怎樣才能寫到0.000的境界呢！！我想也許在找shortest path的部分還可以再更快一點。

REFERENCES

117 - The Postal Worker Rings Once
Euler Circuit / Euler Path
Handshaking lemma

CODE

#include <stdio.h>
#include <string.h>

#define MAX 26
#define MAX_LEN 1000

int t[MAX][MAX], od[2];

void initialize(void);
int odegree(void);
int shortest(int a, int b);

int main(){
  int i, j;
  int sum, len;
  char s[MAX_LEN];
  
  sum = 0;
  initialize();
  while( scanf("%s", s) != EOF ){
    if( strcmp(s, "deadend") == 0 ){
      if( odegree() == 1 ){
        sum += shortest(od[0], od[1]);
        printf("%d\n", sum);
      }
      else
        printf("%d\n", sum);
      
      sum = 0;
      initialize();
    }/*output*/
    else{
      len = strlen(s);
      sum += len;
      t[ s[0]-'a' ][ s[len-1]-'a' ] = t[ s[len-1]-'a' ][ s[0]-'a' ] = len;
    }/*read data*/
  }/*while input data*/
  
  exit(0);
}

void initialize(void){
  int i, j;
  
  for(i=0; i<MAX; i++)
    for(j=0; j<MAX; j++)
      t[i][j] = 0;
  return;
}

int odegree(void){
  int i, j, k, d;
  
  d = 0;
  for(i=0; i<MAX; i++){
    k = 0;
    for(j=0; j<MAX; j++)
      if( t[i][j] > 0 )
        k++;
    if( k%2 == 1 )
      od[d++] = i;
  }
  
  if( d > 0 )
    return 1;
  return 0;
}

int shortest(int a, int b){
  int i, j, k, tmp;
  
  for(k=0; k<MAX; k++){
    for(i=0; i<MAX; i++){
      for(j=0; j<MAX; j++){
        if( t[i][k]*t[k][j] != 0 ){
          tmp = t[i][k] + t[k][j];
          if( tmp < t[i][j] || t[i][j] == 0 )
            t[i][j] = tmp;
        }
      }/*j*/
    }/*i*/
  }/*k*/
  
  return t[a][b];
}