2316 도시 왕복하기

1과 2를 왕복하는데 한번 갔던 도시는 다시 가지 않을 때 경우의 수를 구하는 문제이다.

길이 양방향 길이므로 2->1로 가는 길이 있다면 1->2로 가는 동일한 경로가 무조건 존재한다.

따라서 source = 1, sink = 2 일 때  들렀던 도시를 check해주며 maximum flow를 구하면 된다.

--------------------------------------------------------------------

어떤 종류인지는 예상이 안되지만 케이스가 추가되어 재채점되었다.

계속해서 틀렸다고 뜨길래 정점을 쪼개는 방식으로(한 도시에 한번만 방문하기 위해) 변경했다.

<코드>

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

#include <stdio.h>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

typedef pair<int, int> pii;

 

int m, p;

struct MF {

    struct E {

        int u, c;

        E *rev;

        E(int u, int c) : u(u), c(c) {}

    };

    int n, s, e;

    vector<vector<E *>> g;

    vector<bool> check;

    MF(int m) {

        n = m;

        s = 0;

        e = 1 + m / 2;

        g.resize(n);

        check.resize(n);

    }

    void add_Edge(int u, int v, int c) {

        E *ori = new E(v, c);

        E *rev = new E(u, 0);

        ori->rev = rev;

        rev->rev = ori;

        g[u].push_back(ori);

        g[v].push_back(rev);

    }

 

    int bfs() {

        vector<bool> ch(n, false);

        vector<pii> f(n, { -1,-1 });

        queue<int> q;

        q.push(s);

        ch[s] = true;

        while (q.size()) {

            int x = q.front();

            q.pop();

            for (int i = 0; i < g[x].size(); i++) {

                if (x == s && g[x][i]->u == e) continue;

                if (!ch[g[x][i]->u] && g[x][i]->c && !check[g[x][i]->u]) {

                    q.push(g[x][i]->u);

                    ch[g[x][i]->u] = true;

                    f[g[x][i]->u] = { x, i };

                }

            }

        }

        if (!ch[e]) return 0;

        int x = e;

        int c = 1;

        while (f[x].first != -1) {

            E *ed = g[f[x].first][f[x].second];

            ed->c --;

            ed->rev->c ++;

            x = f[x].first;

        }

        return c;

    }

    int flow() {

        int ans = 0;

        while (1) {

            int f = bfs();

            if (!f) break;

            ans += f;

        }

        return ans;

    }

};

 

int main() {

    scanf("%d%d", &m, &p);

    MF mf(2*m);

    mf.add_Edge(0, m, 2e9);

    mf.add_Edge(1, 1 + m, 2e9);

    for (int i = 2; i < m; i++) 

        mf.add_Edge(i, i + m, 1);

    while (p--) {

        int a, b;

        scanf("%d%d", &a, &b);

        a--; b--;

        mf.add_Edge(a + m, b, 1);

        mf.add_Edge(b + m, a, 1);

    }

    printf("%d\n", mf.flow());

    return 0;

}

Colored by Color Scripter

cs