０１ ２色塗りグラフ、ベルマンフォード法

例によってあり本の写経

２色塗り

vector<int> G[MAX_V];

int V;

int color[MAX_V];

// color edge c or -c

bool dfs(int v, int c) {

  // paint edge with color "c"

  color[v] = c;

  for (int i = 0; i < G[v].size; i++) {

　//隣り合う辺で頂点がcのものはスルー

    if (color[G[v][i]] == c) return false;

    //頂点が色なしの０場合、C色の頂点と隣合うので逆の色として―Cで塗る

    if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;

  }

  return true;

}

void solve() {

  for (int i = 1; i<V; i++) {

    if (color[i] == 0) {

      // if edge i is not colored, paint edge with "1"

      if (!dfs(i,1)) {

printf("No\n");

return;

      }

    }

  }

  printf("Yes\n");

}

ベルマンフォード法

// a cost from edge "from" to edge "to" 

struct {int from, to cost; };

edge es[MAX_E]; // side

int d[MAX_V]; //shortest distance

int V, E; // V: qty of edge, E: qty of side

// Calculate distance from edge "s" to each edge

void shortest_path(int s){

  for (int i=0; i<V; i++) d[i] = INF;

  d[s] = 0;

  while(true){

    bool update = false;

    for (int j=0; j< E; j++) {

      edge e = es[j];

      if (d[e.from] != INF && d[e.to] > d[e.from] + e.cost) {

　　//移動先の頂点までかかるコストが移動先の頂点が持っている総コストより小さいかどうか

d[e.to] = d[e.from] + e.cost;

update = true;

      }

    }

    if (!update) break;

  }

}

// 閉路を見つけるため。V個頂点がある場合、開いて入ればV-1個の捜査で終わる。V個を捜査するのであれば、それは閉路となる。

bool find_negativeloop() {

  memset(d, 0, sizeof(d));

  for (int i=0; i<V; i++){

    for (int j=0; j<E; j++){

      edge e = es[j];

      if (d[e.to] > d[e.from] + e.cost) {

d[e.to] = d[e.from] + e.cost;

if (i == V-1) return true;　//配列だから、マイナ１でV個扱い

      }

    }

  }

  return false;

}