グラフを使った解法を勉強した. グラフの表現方法として隣接行列と隣接リストの2つがあって, 最短経路問題を特にはベルマンフォード法, ダイクストラ法, ワーシャル-フロイド法があり, 最小全域木問題を特にはプリム法とクラスカル法がある. この一部を使った演習問題を紹介する.
二部グラフ判定
深さ優先探索を用いて, 隣接している頂点をどんどん塗っていく. グラフは隣接リストを使って表現されている.
#include <iostream>
#include <vector>
using namespace std;
const int MAX_V = 10000;
vector<int> G[MAX_V];
int V, E;
int color[MAX_V];
//頂点を1と-1で塗っていく
bool dfs(int v, int c) {
color[v] = c;
for (int i = 0; i < G[v].size(); i++) {
// 隣接している頂点が同じ色ならfalse
if (color[G[v][i]] == c) {
return false;
}
// 隣接している頂点がまだ塗られていないなら-cで塗る
if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) {
return false;
}
}
return true;
}
int main(int argc, char const *argv[]) {
cin >> V >> E;
for (int i = 0; i < E; i++) {
int s, t;
cin >> s >> t;
G[s].push_back(t);
G[t].push_back(s);
}
for (int i = 0; i < V; i++) {
if (color[i] == 0) {
if (!dfs(i, 1)) {
printf("No\n");
return 1;
}
}
}
printf("Yes\n");
return 0;
}Roadblocks
道を辺として, 交差点を頂点として2番目に短い経路を求める問題. 基本的にはダイクストラ法を用いるが, ２番目に短い経路も記憶しておくところがみそ.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N = 1000;
const int INF = 99999999;
struct edge {
int to, cost;
};
typedef pair<int, int> P; // firstは最短距離, secondは頂点の番号
int N, R, E;
vector<edge> G[MAX_N]; // グラフの隣接リスト表現
int dist[MAX_N];
int dist2[MAX_N];
void read() {
cin >> N >> R >> E;
for (int i = 0; i < E; i++) {
int s, t, c;
cin >> s >> t >> c;
edge x, y;
x.to = s;
y.to = t;
x.cost = c;
y.cost = c;
G[s].push_back(y);
G[t].push_back(x);
}
}
void solve() {
priority_queue<P, vector<P>, greater<P> > que;
fill(dist, dist + N, INF);
fill(dist2, dist2 + N, INF);
// 発ノード
dist[0] = 0;
que.push(P(0, 0));
while (!que.empty()) {
P p = que.top();
que.pop();
int v = p.second;
int d = p.first;
if (dist2[v] < d) {
// 2番目の最短路より長い
continue;
}
// vと隣接している頂点を更新
for (int i = 0; i < G[v].size(); i++) {
edge e = G[v][i];
int d2 = d + e.cost;
if (dist[e.to] > d2) {
// 最短より短い場合
swap(dist[e.to], d2);
que.push(P(dist[e.to], e.to));
}
if (dist2[e.to] > d2 && dist[e.to] < d2) {
// ２番目より短い場合
dist2[e.to] = d2;
que.push(P(dist2[e.to], e.to));
}
}
}
printf("%d\n", dist2[N - 1]);
}
int main(int argc, char const *argv[]) {
read();
solve();
return 0;
}Conscription
人を頂点として親密度をコスト付きの辺として, 最小全域木をもとめる問題. この時, コストの高い辺を使いたいのでコストの正負を反転させる. また, この問題は男と女が分けられているが, 特殊な構造を使わなかった.
最小全域木を求めるときはクラスカル法を用いた. クラスカル法はUnionFind木の手法を応用している.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAX_N = 50000;
const int MAX_E = 50000;
const int MAX_R = 50000;
// union find
// --------------------------------------------
int par[MAX_N];
int depth[MAX_N];
void init_union_find(int n) {
for (int i = 0; i < n; i++) {
par[i] = i;
depth[i] = 0;
}
}
int find(int x) {
if (par[x] == x) {
return x;
} else {
return par[x] = find(par[x]);
}
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (depth[x] < depth[y]) {
par[x] = y;
} else {
par[y] = x;
if (depth[x] == depth[y]) depth[x]++;
}
}
bool same(int x, int y) { return find(x) == find(y); }
struct edge {
int u, v, cost;
};
bool comp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; }
edge es[MAX_E];
int V, E;
int kruskal() {
sort(es, es + E, comp);
init_union_find(V);
int res = 0;
for (int i = 0; i < E; i++) {
edge e = es[i];
if (!same(e.u, e.v)) {
unite(e.u, e.v);
res += e.cost;
}
}
return res;
}
int N, M, R;
int x[MAX_R], y[MAX_R], d[MAX_R];
void read() {
cin >> N >> M >> R;
for (int i = 0; i < R; i++) {
cin >> x[i] >> y[i] >> d[i];
}
}
void solve() {
V = N + M;
E = R;
for (int i = 0; i < E; i++) {
es[i] = (edge){x[i], N + y[i], -d[i]};
}
printf("%d\n", 10000 * (V) + kruskal());
}
int main(int argc, char const* argv[]) {
read();
solve();
return 0;
}Layout
牛を頂点と考え, 牛の番号, 仲の良さ, 仲の悪さをコストつきの辺として最短経路を求める問題. 発想としては, 全てを制約条件に落としこんだ結果, 両辺に変数が1つずつしか現れていないことに着目する.
今回は負の辺があるのでベルマンフォード法を用いる. 負閉路が存在するかどうかは, 牛の数だけupdateを行ったあとにも更新があるかどうかで判断する.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAX_ML = 10000;
const int MAX_MD = 10000;
const int MAX_N = 1000;
const int INF = 99999999;
int N, ML, MD;
int AL[MAX_ML], BL[MAX_ML], DL[MAX_ML];
int AD[MAX_MD], BD[MAX_MD], DD[MAX_MD];
int d[MAX_N];
bool updated;
void read() {
cin >> N >> ML >> MD;
for (int i = 0; i < ML; i++) {
cin >> AL[i] >> BL[i] >> DL[i];
}
for (int i = 0; i < MD; i++) {
cin >> AD[i] >> BD[i] >> DD[i];
}
}
void update(int& x, int y) {
if (x > y) {
x = y;
updated = true;
}
}
void bellmanford() {
for (int k = 0; k <= N; k++) {
updated = false;
// i+1からiへコスト0
for (int i = 0; i + 1 < N; i++) {
if (d[i + 1] < INF) {
update(d[i], d[i + 1]);
}
}
// ALからBLへコストDL
for (int i = 0; i < ML; i++) {
if (d[AL[i] - 1] < INF) {
update(d[BL[i] - 1], d[AL[i] - 1] + DL[i]);
}
}
// BDからADへコスト-DD
for (int i = 0; i < MD; i++) {
if (d[BD[i] - 1] < INF) {
update(d[AD[i] - 1], d[BD[i] - 1] - DD[i]);
}
}
}
}
void solve() {
// 負閉路チェック
fill(d, d + N, 0);
bellmanford();
if (updated) {
printf("%d\n", -1);
return;
}
fill(d, d + N, INF);
d[0] = 0;
bellmanford();
int res = d[N - 1];
if (res == INF) {
res = -2;
}
printf("%d\n", res);
}
int main(int argc, char const* argv[]) {
read();
solve();
return 0;
}感想
最後の牛の並びを最短経路問題に変換する方法はむずすぎる….