Advertisement
Guest User

Serial Implementation of Stable Marriage algo

a guest
Nov 26th, 2015
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 1.14 KB | None | 0 0
  1. package main
  2.  
  3. import "fmt"
  4.  
  5. const N = 500
  6.  
  7. var men = [N][N + 2]int{}
  8. var women = [N][N + 2]int{}
  9.  
  10. func fix(man int) {
  11.     i := man
  12.     for j := men[i][N+1] + 1; j < N; j++ {
  13.         k := men[i][j]
  14.         men[i][N+1] = j
  15.         if women[k][N] == -1 {
  16.             women[k][N] = i
  17.             men[i][N] = k
  18.             break
  19.         } else {
  20.             eng := women[k][N]
  21.             if women[k][eng] > women[k][i] {
  22.                 women[k][N] = i
  23.                 men[i][N] = k
  24.                 fix(eng)
  25.                 break
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. func main() {
  32.     for i := 0; i < N; i++ {
  33.         for j := 0; j < N; j++ {
  34.             fmt.Scanf("%d\n", &men[i][j])
  35.         }
  36.         men[i][N], men[i][N+1] = -1, -1
  37.     }
  38.     for i := 0; i < N; i++ {
  39.         for j := 0; j < N; j++ {
  40.             t := 0
  41.             fmt.Scanf("%d\n", &t)
  42.             women[i][t] = j
  43.         }
  44.         women[i][N], women[i][N+1] = -1, -1
  45.     }
  46.     for i := 0; i < N; i++ {
  47.         for j := 0; j < N; j++ {
  48.             k := men[i][j]
  49.             men[i][N+1] = j
  50.             if women[k][N] == -1 {
  51.                 women[k][N] = i
  52.                 men[i][N] = k
  53.                 break
  54.             } else {
  55.                 eng := women[k][N]
  56.                 if women[k][eng] > women[k][i] {
  57.                     women[k][N] = i
  58.                     men[i][N] = k
  59.                     fix(eng)
  60.                     break
  61.                 }
  62.             }
  63.         }
  64.     }
  65.     for i := 0; i < N; i++ {
  66.         fmt.Printf("%d %d\n", i, men[i][N])
  67.     }
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement