티스토리 뷰

알고리즘 관련/BOJ

BOJ)5398 틀렸습니다

JASON 자손9319 2017. 2. 11. 14:02

문제: icpc.me/5398


충돌되는 단어들에 대하여 가로단어와 세로단어로 이루어진 이분 그래프를 형성시켜준 뒤 mincut을 구해주어 모든단어-mincut을 구해주면 되는 문제이다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int t, h, v, x, y;
char a[2001][2001];
int c[2001][2001];
int check[1001];
int backmatch[1001];
vector<vector<int>> vt;
bool dfs(int here) {
    if (here == -1return true;
    for (int next : vt[here]) {
        if (check[next])continue;
        check[next] = true;
        if (dfs(backmatch[next])) {
            backmatch[next] = here;
            return true;
        }
    }
    return false;
}
int bmatch() {
    memset(backmatch, -1sizeof(backmatch));
    int ret = 0;
    for (int i = 1; i <= v; i++) {
        memset(check, 0sizeof(check));
        if (dfs(i))
            ret++;
    }
    return ret;
}
int main() {
    scanf("%d"&t);
    while (t--) {
        vt.clear();
        memset(a, NULL, sizeof(a));
        scanf("%d%d"&h, &v);
        vt.resize(max(h, v) + 1);
        for (int i = 1; i <= h; i++) {
            scanf("%d%d"&x, &y);
            char b[2001];
            scanf("%s"&b);
            int j = strlen(b);
            for (int k = 0; k < j; k++) {
                a[x + k][y] = b[k];
                c[x + k][y] = i;
            }
        }
        for (int i = 1; i <= v; i++) {
            scanf("%d%d"&x, &y);
            char b[2001];
            scanf("%s"&b);
            int j = strlen(b);
            for (int k = 0; k < j; k++) {
                if (a[x][y + k] != NULL&&a[x][y + k] != b[k]) {
                    vt[i].push_back(c[x][y + k]);
                }
            }
        }
        printf("%d\n", h + v - bmatch());
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2262 토너먼트 만들기  (0) 2017.02.15
BOJ)14226 이모티콘  (0) 2017.02.14
BOJ)5398 틀렸습니다  (0) 2017.02.11
BOJ)10266 시계 사진들  (0) 2017.02.08
BOJ)1305 광고  (0) 2017.02.08
BOJ)11479 서로 다른 부분 문자열의 개수2  (0) 2017.02.08
댓글
댓글쓰기 폼