같은 값을 갖지만, 변수 초기화를 변수만 다르게 이용해서 쓰면 다른 결과가 나옵니다.(MATCHFIX 문제)

  • Harder
    Harder

    제 코드에서 이 부분이 문제입니다.

    for (int i = wins[0]; i <= wins[0] + cnt; i++){         
                if (i < maxW + 1) {
                flag = 0;
                continue;
                }
    
                updateC(flag, i);
                if (go() == M) {
                    ans = i; break;
                }
                flag = 1;
            }
    

    위의 코드는 올바르게 정답이라고 나오지만, 아래 코드를 보시면..

    for (int i = maxW + 1; i <= wins[0] + cnt; i++){
                /*
                if (i < maxW + 1) {
                flag = 0;
                continue;
                }
                */
                updateC(flag, i);
                if (go() == M) {
                    ans = i; break;
                }
                flag = 1;
            }
    

    같은 동작방식임에도 불구하고 오답으로 나옵니다.
    혹시 제가 놓친 부분이 있나요..?
    아래엔 제 코드 전부를 첨부합니다.
    (참고로 정답을 받은 코드와 위의 부분만 다른 코드로, 오답을 받은 코드입니다.)

    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<cstring>
    using namespace std;
    struct Edge {
        int to, c, f;
        Edge(int to, int c, int f) : to(to), c(c), f(f) {}
        Edge* r;
        int pflow() { return c - f; }
        void push(int val) {
            f += val, r->f -= val;
        }
    };
    int S, T, C, N, M, wins[20], maxC, maxF, maxW, cnt, ans;
    Edge* idx[20];
    vector<vector<Edge*>> adj;
    void addE(int a, int b, int c) {
        Edge* ab = new Edge(b, c, 0), *ba = new Edge(a, 0, 0);
        ab->r = ba;
        ba->r = ab;
        adj[a].push_back(ab);
        adj[b].push_back(ba);
        if (b == T) idx[a - M] = ab;
    }
    void updateC(int m, int val) {
        maxC = 0;
        for (int i = M; i < N + M; i++) {
            int newC = val - wins[i - M] - (i != M);
            if (!m) addE(i, T, newC);
            else idx[i - M]->c = newC;
        }
    }
    int go() {
        while (1) {
            vector<pair<int, int>> p(T + 5, make_pair(-1, -1));
            queue<int> q;
            q.push(S); p[S] = make_pair(S, S);
            while (!q.empty() && p[T].first == -1) {
                int now = q.front(); q.pop();
                for (int i = 0; i < adj[now].size(); i++) {
                    Edge* nv = adj[now][i];
                    if (nv->pflow() > 0 && p[nv->to].first == -1)
                        q.push(nv->to), p[nv->to] = make_pair(now, i);
                }
            }
            if (p[T].first == -1) {
                break;
            }
            int minF = 1;
            for (int i = T; i != S; i = p[i].first)
                adj[p[i].first][p[i].second]->push(minF);
            maxF += minF;
        }
        return maxF;
    }
    int main() {
        scanf("%d", &C);
        while (C--) {
            scanf("%d %d", &N, &M);
    
            memset(wins, 0, sizeof(wins));
            maxC = maxF = maxW = cnt = ans = 0;
            adj.clear();
    
            S = N + M + 5, T = N + M + 10;
            adj.resize(T + 5);
    
            for (int i = 0; i < N; i++) {
                scanf("%d", &wins[i]);
                if (i) maxW = max(maxW, wins[i]);
            }
            for (int i = 0, a, b; i < M; i++) {
                scanf("%d %d", &a, &b);
                if (!a || !b) cnt++;
                addE(S, i, 1);
                addE(i, M + a, 1), addE(i, M + b, 1);
            }
            int flag = 0; ans = -1;
            for (int i = maxW + 1; i <= wins[0] + cnt; i++){
                /*
                if (i < maxW + 1) {
                flag = 0;
                continue;
                }
                */
                updateC(flag, i);
                if (go() == M) {
                    ans = i; break;
                }
                flag = 1;
            }
            printf("%d\n", ans);
        }
        return 0;
    }
    

    7년 전
3개의 댓글이 있습니다.
  • seico75
    seico75

    win[0] > maxW + 1 인 경우는 두 개가 다른 결과나 나올 것 같습니다.


    7년 전 link
  • Harder
    Harder

    제가봤을때는 그럴경우에 두 코드에서 작동되는 코드가 일치하는데 자세히 설명 가능하신가요?? 참고로 flag는 0으로 초기화되어있습니다 두 코드 전부.


    7년 전 link
  • seico75
    seico75

    위 코드는 updateC가 불리는 i의 범위가
    max( win[0], maxW + 1) ~ win[0] + cnt
    이고
    아래 코드는 updateC가 불리는 i의 범위가
    maxW+1 ~ win[0] + cnt
    으로 보입니다.

    따라서 win[0] > maxW + 1 인 경우
    win[0] ~ win[0] + cnt .vs. maxW + 1 ~ win[0] + cnt
    로 차이가 날 것 같습니다.


    7년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.