2014/08/15の進捗

2251.cc

void init() {
  REP(i, VMAX) {
    G[i].clear();
  }
  REP(i, LMAX) {
    ptime[i] = req[i] = 0;
  }
  REP(i, NMAX) {
    REP(j, NMAX) {
      dist[i][j] = (i == j ? 0 : INF);
    }
  }
}

int From(int n, int i) {
  return 2 + i;
}

int To(int n, int i) {
  return 2 + n + i;
}

int main() {
  int n, m, l;

  while (cin >> n >> m >> l and n) {
    init();
    REP(i, m) {
      int u, v, d;
      cin >> u >> v >> d;
      dist[u][v] = dist[v][u] = d;
    }

    REP(k, n) REP(i, n) REP(j, n) {
      dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    }

    REP(i, l) {
      cin >> req[i] >> ptime[i];
    }

    V = 2 * l;

    REP(bef, l) REP(aft, l) {
      if (bef == aft) continue;
      if (ptime[bef] < ptime[aft] and 
          ptime[aft] - ptime[bef] >= dist[req[bef]][req[aft]]) {
        add_edge(bef, l + aft);
      }
    }

    cout << l - bipartite_matching() << endl;
  }
}

2311.cc

#include<iostream>
#include<string>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

char board[8][8];

int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1},
    dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0};

char enemy(char cookie) {
  return cookie == 'o' ? 'x' : 'o';
}

bool put_and_put(char cookie, int x, int y, int dir) {
  if (x < 0 or 7 < x or y < 0 or 7 < y or
      board[x][y] == '.') {
    return false;
  } else if (board[x][y] == enemy(cookie)) {
    if (put_and_put(cookie, x + dx[dir], y + dy[dir], dir)) {
      board[x][y] = cookie;
      return true;
    } else {
      return false;
    }
  } else {
    return true;
  }
}


void put(char cookie, int x, int y) {
  if (board[x][y] != '.') return;
  board[x][y] = cookie;
  REP(dir, 8) {
    put_and_put(cookie, x + dx[dir], y + dy[dir], dir);
  }
}

int turn_and_turn(char cookie, int x, int y, int dir) {
  if (x < 0 or 7 < x or y < 0 or 7 < y or
      board[x][y] == '.') {
    return -1; 
  } else if (board[x][y] == enemy(cookie)) {
    int t = turn_and_turn(cookie, x + dx[dir], y + dy[dir], dir);
    return t == -1 ? -1 : t + 1;
  } else if (board[x][y] == cookie) {
    return 0;
  }
}


int turnables(char cookie, int x, int y) {
  if (board[x][y] != '.') return 0;
  int ans = 0;
  REP(dir, 8) {
    int t = turn_and_turn(cookie, x + dx[dir], y + dy[dir], dir);
    ans += (t < 0 ? 0 : t);
  }
//  cout << "turnables(" << cookie << ", " << x << ", " << y
  //  << ") = " << ans << endl;
  return ans;
}

bool mami() {
  int x, y;
  int ts = 0;
  REP (j, 8) REP(i, 8) {
    if (turnables('o', i, j) > ts) {
      ts = turnables('o', i, j);
      x = i, y = j;
    }
  }
  if (ts > 0) {
    put('o', x, y);
    return true;
  } else {
    return false;
  }
}

bool charlotte() {
  int x, y;
  int ts = 0;
  for (int j = 7; j >= 0; j--) {
    for (int i = 7; i >= 0; i--) {
      if (turnables('x', i, j) > ts) {
        ts = turnables('x', i, j);
        x = i, y = j;
      }
    }
  }
  if (ts > 0) {
    put('x', x, y);
    return true;
  } else {
    return false;
  }
}

int main() {
  REP(y, 8) {
    string row;
    cin >> row;
    REP(x, 8) {
      board[x][y] = row[x];
    }
  }

  int pass = 0;

  while (pass < 2) {
    pass = (mami() ? 0 : pass + 1);
/*  REP(y, 8) {
    REP(x, 8) {
      cout << board[x][y];
    }
    cout << endl;
  }*/
    pass = (charlotte() ? 0 : pass + 1);
/*  REP(y, 8) {
    REP(x, 8) {
      cout << board[x][y];
    }
    cout << endl;
  }*/
  }

  REP(y, 8) {
    REP(x, 8) {
      cout << board[x][y];
    }
    cout << endl;
  }
}