UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#206832#3694. 染色 2Anthonyyan100623ms2388kbC++111.4kb2024-07-25 18:58:492024-07-25 20:13:33

answer

#include <bits/stdc++.h>
using namespace std;
int main(int, char const *[])
{
  int n, m;
  cin >> n >> m;
  vector<string> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  vector<vector<int>> G(n * m + 1);
  vector<int> color(n * m + 1, -1);
  vector<int> match(n * m + 1);
  vector<int> vis(n * m + 1);
  function<int(int, int)> index = [&](int x, int y)
  {
    return x * m + y + 1;
  };
  function<void(int, int)> addEdge = [&](int u, int v)
  {
    G[u].push_back(v);
    G[v].push_back(u);
    return;
  };
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    {
      if (a[i][j] == 'x')
        continue;
      int x = index(i, j);
      if (i != 0 && a[i - 1][j] != 'x')
        addEdge(x, index(i - 1, j));
      if (j != 0 && a[i][j - 1] != 'x')
        addEdge(x, index(i, j - 1));
    }
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
    {
      int u = index(i, j);
      sort(G[u].begin(), G[u].end());
    }
  function<bool(int, int)> dfs = [&](int u, int tag)
  {
    if (vis[u] == tag)
      return false;
    vis[u] = tag;
    for (auto v : G[u])
    {
      if (!match[v] || dfs(match[v], tag))
      {
        match[v] = u;
        return true;
      }
    }
    return false;
  };
  int ans = 0;
  for (int i = 1; i <= n * m; i++)
    if (dfs(i, i))
      ans++;
  cout << (ans >> 1);
  return 0;
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1260kb

input:

4 5
.....
x.x.x
x.x.x
.....

output:

6

result:

ok "6"

Test #2:

score: 5
Accepted
time: 0ms
memory: 1264kb

input:

3 6
.x...x
x.x.x.
.....x

output:

3

result:

ok "3"

Test #3:

score: 5
Accepted
time: 0ms
memory: 1256kb

input:

1 20
..xxx.xx...x....x..x

output:

5

result:

ok "5"

Test #4:

score: 5
Accepted
time: 0ms
memory: 1264kb

input:

5 4
....
x.x.
..x.
.x..
....

output:

8

result:

ok "8"

Test #5:

score: 5
Accepted
time: 8ms
memory: 1860kb

input:

10 1000
....x..........x.x....x.x....x.......x.........................................x.....x.........

output:

4321

result:

ok "4321"

Test #6:

score: 5
Accepted
time: 5ms
memory: 1624kb

input:

10 1000
x..x..x................x..x...............x..x......x...x...x...x.x..x......xx.............x...

output:

3558

result:

ok "3558"

Test #7:

score: 5
Accepted
time: 2ms
memory: 1596kb

input:

10 1000
.xxx.x.x.xxx.xxx....xx.xxx.x....x..xx.........x.xxxxxx.xxxx....xx..xx...x....x.....xxxxx.xx....

output:

2754

result:

ok "2754"

Test #8:

score: 5
Accepted
time: 3ms
memory: 2388kb

input:

10000 1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
.
.
.
.
.
.
.
.
.
.
.
.
.
x
.
.
.
.
.
.
.
.
x
.
...

output:

4275

result:

ok "4275"

Test #9:

score: 5
Accepted
time: 211ms
memory: 1856kb

input:

100 100
.........x.................................x........x.......x............x.....................

output:

4567

result:

ok "4567"

Test #10:

score: 5
Accepted
time: 102ms
memory: 1860kb

input:

100 100
......x..x...x.x........x...x..........x............x......x.....x..........x..x...............

output:

4078

result:

ok "4078"

Test #11:

score: 5
Accepted
time: 9ms
memory: 1628kb

input:

100 100
......xxx.............x...x.xx.xx......x............x......x..x..x..........x.x...x...x...xx...

output:

3593

result:

ok "3593"

Test #12:

score: 5
Accepted
time: 4ms
memory: 1604kb

input:

100 100
.x..xxx.....x.x....x..x.....x..x...x.x..x.x...x.x.x...x..x.....x.x.....x....x.x..x.x.xx........

output:

3055

result:

ok "3055"

Test #13:

score: 5
Accepted
time: 48ms
memory: 1860kb

input:

100 100
...............x......x...xx.x.x..xx.......x......x.......x............x..x.xx...x...x.x.x.x...

output:

3892

result:

ok "3892"

Test #14:

score: 5
Accepted
time: 46ms
memory: 1856kb

input:

101 99
.x.x...x.....x.........x.................x.....x.....x...x.x...x...x.....x.............x........

output:

3303

result:

ok "3303"

Test #15:

score: 5
Accepted
time: 9ms
memory: 1636kb

input:

101 99
...x.............x.x...x.....x...x.x.............x.x.x.....x...x.x...........x.x.....x.....x....

output:

2801

result:

ok "2801"

Test #16:

score: 5
Accepted
time: 3ms
memory: 1604kb

input:

101 99
.....x.....x...x.x.x.........x.x.x.x.x...x.x...x.........x.x.x.x.x.......x.x.x.........x.x......

output:

2221

result:

ok "2221"

Test #17:

score: 5
Accepted
time: 3ms
memory: 1592kb

input:

101 99
...x.x...x.x.x.x.x...x.x.x.x.x.x.x.x.....x.x.x...x.x.x.....x...x.....x.x...x...x.x.x...x.x.x....

output:

1634

result:

ok "1634"

Test #18:

score: 5
Accepted
time: 0ms
memory: 1592kb

input:

101 99
.x.x.x.x.x.x.x...x.x...x.x.x.x...x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x...x.x.x...x.x.x.x.x.x.x....

output:

1074

result:

ok "1074"

Test #19:

score: 5
Accepted
time: 0ms
memory: 1592kb

input:

101 99
.x.x...x.x.x.x.x...x.x.x.x.x.x.x.x.x.x.x...x.x.x.x.x.x.x.x.x.x...x.x.x.x.x.x...x.x.x...x.x.x....

output:

554

result:

ok "554"

Test #20:

score: 5
Accepted
time: 170ms
memory: 1860kb

input:

100 100
...............x.................................x.......................................x.....

output:

4500

result:

ok "4500"