Top
yukicoder No.483「マッチ並べ」
nn 個の長さ 11 のマッチ棒を二つの格子点が始点と終点になるように置いたとき、頭薬が重ならないようにすることができるかどうか判定してください。
・1≤n≤1001 \le n \le 100
・1≤1 \le 格子点の xyxy 座標 ≤100\le 100

機械的に 2-SAT とか最大マッチングとかでやる方が頭を使わずに出来る気がする。

---
(ΦωΦ)＜二者択一を繰り返した結果の中に目的を達成できるものがあるかどうかを知りたいので 2-SAT.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <algorithm>
using namespace std;

// 強連結成分 (Strongly Connected Components) 分解
class SCC {
  int n;
  int scc_count; // 強連結成分の個数
  vector<vector<int>> fG, rG;
  vector<bool> used;
  vector<int> order; // 属する強連結成分のトポロジカル順序
  vector<int> vertices; // 帰りがけ順の並び
  void dfs(int u);
  void rdfs(int v, int k);
public:
  SCC(int n); // 頂点数が n のグラフ
  void add_edge(int u, int v); // u から v に辺を張る
  void solve(); // 強連結成分分解する
  vector<int> get_order(); // solve() の後に呼び出してトポロジカル順序を返す。同じ強連結成分は同じ値になる。
  vector<vector<int>> restore_sccs(); // solve() の後に呼び出して強連結成分をトポロジカル順序で返す
};

SCC::SCC(int n) : n(n) {
  fG.assign(n, vector<int>());
  rG.assign(n, vector<int>());
}

void SCC::add_edge(int u, int v) {
  fG[u].push_back(v);
  rG[v].push_back(u);
}

void SCC::dfs(int u) {
  used[u] = true;
  for(int v : fG[u]) {
    if(!used[v]) { dfs(v); }
  }
  vertices.push_back(u);
}

void SCC::rdfs(int v, int k) {
  used[v] = true;
  order[v] = k;
  for(int u : rG[v]) {
    if(!used[u]) { rdfs(u, k); }
  }
}

vector<int> SCC::get_order() {
  return order;
}

void SCC::solve() {
  used.assign(n, false);
  order.assign(n, 0);
  vertices.clear();
  for(int u=0; u<n; ++u) {
    if(!used[u]) { dfs(u); }
  }
  used.assign(n, false);
  scc_count = 0;
  for(int i=vertices.size()-1; i>=0; --i) {
    if(!used[vertices[i]]) { rdfs(vertices[i], scc_count++); }
  }
}

vector<vector<int>> SCC::restore_sccs() {
  vector<vector<int>> res(scc_count, vector<int>()); // res[scc_count][]
  for(int i=0; i<n; ++i) {
    res[order[i]].push_back(i);
  }
  return res;
}

// 2-SAT
class TwoSAT {
  int n;
  SCC g;
public:
  TwoSAT(int n);
  void add_clause(bool flag0, int x0, bool flag1, int x1); // (x0 | x1)という節を追加する
  vector<bool> solve(); // 戻り値: 可能なら真偽の割り当て、不可能なら空配列
};

TwoSAT::TwoSAT(int n) : n(n), g(2*n) {}

void TwoSAT::add_clause(bool flag0, int x0, bool flag1, int x1) {
  g.add_edge(x0 + n * !flag0, x1 + n * flag1); // !x0 => x1
  g.add_edge(x1 + n * !flag1, x0 + n * flag0); // !x1 => x0
  // メモ: (x0 | x1) = (!x0 => x1 & !x1 => x0)
}

vector<bool> TwoSAT::solve() {
  g.solve();
  vector<int> order = g.get_order();
  vector<bool> res(n);
  for(int i=0; i<n; ++i) {
    if(order[i] == order[i+n]) { return vector<bool>(); } // 充足不可能
    if(order[i] > order[i+n])  { res[i] = true; }
  }
  return res;
}

int main(void) {
  int n; scanf("%d", &n);
  vector<int> r0(n), c0(n), r1(n), c1(n);
  for(int i=0; i<n; ++i) {
    scanf("%d%d%d%d", &r0[i], &c0[i], &r1[i], &c1[i]);
  }
  TwoSAT sat(n);
  for(int i=0; i<n; ++i) {
    for(int j=i+1; j<n; ++j) {
      // 頭薬側を有向グラフの矢尻側とする。
      // マッチ棒をそのまま置く((r0,c0) -> (r1,c1))ときは true, 
      // 反転させる((r0,c0) <- (r1,c1))ときは false.
      // 頭薬が重なるときに節を追加する。
      if(r0[i] == r0[j] && c0[i] == c0[j]) { sat.add_clause(false, i, false, j); }
      if(r1[i] == r0[j] && c1[i] == c0[j]) { sat.add_clause(true,  i, false, j); }
      if(r0[i] == r1[j] && c0[i] == c1[j]) { sat.add_clause(false, i, true,  j); }
      if(r1[i] == r1[j] && c1[i] == c1[j]) { sat.add_clause(true,  i, true,  j); }
    }
  }
  bool able = sat.solve().size();
  puts(able ? "YES" : "NO");
  return 0;
}

---
(ΦωΦ)＜マッチングと見なして最大流。
ソースとシンクを作る。
ソースから nn 個のマッチ棒にコスト 11 で辺を張る。
nn 個のマッチ棒のそれぞれから始点と終点へコスト 11 で辺を張る。
格子点の全てからシンクへコスト 11 で辺を張る。
フローを流して nn の量が全部シンクまで来るかどうかを調べる。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

constexpr int inf = 987654321;

struct Edge {
  int dst, rev;
  int capa;
};

class Graph {
protected:
  int size;
  vector<vector<Edge>> g;
public:
  Graph(int size) : size(size) { g.resize(size); }
  void add_edge(int src, int dst, int capa);
  int max_flow(int s, int t) { throw; }
};

class Dinic : public Graph {
  vector<int> level, iter;
  void bfs(int s);
  int dfs(int v, int t, int flow);
public:
  Dinic(int size) : Graph(size) {}
  int max_flow(int s, int t);
};

void Graph::add_edge(int src, int dst, int capa) {
  g[src].push_back(Edge({dst, int(g[dst].size()),   capa}));
  g[dst].push_back(Edge({src, int(g[src].size())-1,    0}));
}

void Dinic::bfs(int s) {
  level.assign(size, -1);
  queue<int> que;
  level[s] = 0;
  que.push(s);
  while(!que.empty()) {
    int v = que.front(); que.pop();
    for(Edge& e : g[v]) {
      if(e.capa > 0 && level[e.dst] < 0) {
        level[e.dst] = level[v] + 1;
        que.push(e.dst);
      }
    }
  }
}

int Dinic::dfs(int v, int t, int flow) {
  if(v == t) { return flow; }
  for(int& i=iter[v], n=g[v].size(); i<n; ++i) {
    Edge& e = g[v][i];
    if(e.capa <= 0 || level[v] >= level[e.dst]) { continue; }
    int d = dfs(e.dst, t, min(flow, e.capa));
    if(d > 0) {
      e.capa -= d;
      g[e.dst][e.rev].capa += d;
      return d;
    }
  }
  return 0;
}

int Dinic::max_flow(int s, int t) {
  int res = 0;
  while(true) {
    bfs(s);
    if(level[t] < 0) { return res; }
    iter.assign(size, 0);
    int flow;
    while((flow = dfs(s, t, inf)) > 0) {
      res += flow;
      if(res >= inf) { return inf; }
    }
  }
}

int main(void) {
  constexpr int N = 111;
  int n; scanf("%d", &n);
  Dinic graph(n + N*N + 2);
  int s = n + N*N,
      t = s + 1;
  for(int i=0; i<n; ++i) {
    int r0, c0, r1, c1; scanf("%d%d%d%d", &r0, &c0, &r1, &c1);
    int x = n + r0 * N + c0,
        y = n + r1 * N + c1;
    graph.add_edge(s, i, 1);
    graph.add_edge(i, x, 1);
    graph.add_edge(i, y, 1);
  }
  for(int r=0; r<N; ++r) {
    for(int c=0; c<N; ++c) {
      int x = n + r * N + c;
      graph.add_edge(x, t, 1);
    }
  }
  int max_flow = graph.max_flow(s, t);
  puts(max_flow == n ? "YES" : "NO");
  return 0;
}

---
(ΦωΦ)＜グラフの各連結成分の頂点数と次数を比較する想定解的なもの。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

// union-find に値を持たせる
struct UnionFind {
  UnionFind() {};
  void unite(int, int);
  int find(int);
  bool contains(int x);
  int size_of(int x);
  int evaluate(int x);
  set<int> key_set(); // parのkeySet
  map<int, int> val;
private:
  map<int, int> par;
};

int UnionFind::find(int x) {
  if(!contains(x)) { par[x] = -1; }
  return par[x] < 0 ? x : (par[x] = find(par[x]));
}

int UnionFind::evaluate(int x) {
  return val[find(x)];
}

void UnionFind::unite(int x, int y) {
  x = find(x), y = find(y);
  if(x == y) { return; }
  if(par[x] > par[y]) { swap(x, y); }
  par[x] += par[y];
  par[y] = x;
  val[x] = val[y] = val[x] + val[y]; // add
}

bool UnionFind::contains(int x) {
  return par.count(x);
}

set<int> UnionFind::key_set() {
  set<int> keySet;
  for(auto&& kv : par) {
    keySet.insert(kv.first);
  }
  return keySet;
}

int UnionFind::size_of(int x) { return -par[find(x)]; }

///
vector<vector<int>> G;
vector<bool> seen;
UnionFind uf;

void rec(int i) {
  if(seen[i]) { return; }
  seen[i] = true;
  for(int j : G[i]) {
    ++uf.val[j]; // 入次数をUnionFindの値として持つ
    rec(j);
  }
}

int main(void) {
  constexpr int N = 111;
  int n; scanf("%d", &n);
  G.assign(N*N, vector<int>());
  seen.assign(N*N, false);
  set<int> vs;
  vector<pair<int, int>> memo;
  for(int i=0; i<n; ++i) {
    int r0, c0, r1, c1; scanf("%d%d%d%d", &r0, &c0, &r1, &c1);
    int x = r0 * N + c0,
        y = r1 * N + c1;
    G[x].push_back(y);
    memo.emplace_back(x, y);
    vs.insert(x);
    vs.insert(y);
  }

  // 値を持たせてから unite したい
  // 値を持たせて…
  for(int v : vs) {
    rec(v);
  }
  // unite
  for(auto&& xy : memo) {
    int x, y; tie(x, y) = xy;
    uf.unite(x, y);
  }

  for(int k : uf.key_set()) {
    // 連結部分ごとのループ
    int V = uf.size_of(k); // 連結部分の頂点数
    int E = uf.evaluate(k); // 連結部分の総入次数
    if(V < E) {
      puts("NO");
      return 0;
    }
  }
  puts("YES");

  return 0;
}

(ΦωΦ)＜つづく