글 읽기 - GG 반례를 못찾겠습니다

ploffer11 4년 전 3

노드 2n개 만들고 정점분할 했습니다.

0 : source

1~n : 진짜노드

n+1~n+n : 가짜노드

2n+1 : sink

로해서 i -> n+i 로 톨게이트 점령 비용으로 capacity 주고 max flow를 구했습니다.

물론 마피아의 start와 end는 source -> start, n+end -> sink 로 연결해 주었구요.

그럼 정점 분할 사이 간선이 capacity == flow 인 친구들이 min cut 후보인데, 이게 여러개일 수 있다는 점을 생각해서 다시 source부터 잔여유량이 있는 곳으로만 가는 bfs를 돌리는데, 어떤 1 <= i <= n 인 노드 i에서 더이상 진행되지 못했을 경우, i->n+i 로 가는 간선을 확인해, flow==cap 일 경우 ans에 추가한 후 정렬해 출력했습니다. 이러면 source에서 도달 가능한 1<=i<=n 중에서, 이미 정점 분할 사이 간선이 꽉 차있어서 못흐르는 (min cut 후보) 인 노드들만 추가될 거라 생각했습니다.

하지만 계속 틀리고 있습니다.

코드가 좀 혼란스러운데 "#define int long long" 이 되어있으며, Dinic 구조체의 solve말고 다른곳은 굳이 보실 필요가 없습니다 (다른 문제들을 수없이 풀어낸 max flow 구조체이기 때문에 실수가 없을 것 같습니다.)

도움주기 힘든 어려운 문제임은 저도 알지만, 계속 틀리고 제 머리로는 반례가 안보여서 질문이라도 올리고 포기하고 다른 문제를 풀러 가도록 하겠습니다.

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
using namespace std;
using ll = long long;
#define int ll
using pii = pair<int, int>;
const ll INF = (ll)1 << 60;
const int MOD = 1e9 + 7;

class Dinic
{
private:
    struct Edge
    {
        int to, rev, cap, flow;
        Edge(int _to, int _cap) : to(_to), cap(_cap), flow(0) {}
    };

    vector<vector<Edge>> adj;
    vector<int> depth, work;

    void bfs()
    {
        fill(depth.begin(), depth.end(), -1);

        queue<int> q;
        q.push(source);
        depth[source] = 0;

        while (!q.empty())
        {
            int s = q.front();
            q.pop();

            for (auto &e : adj[s])
            {
                if (e.cap - e.flow > 0 && depth[e.to] == -1)
                {
                    depth[e.to] = depth[s] + 1;
                    q.push(e.to);
                }
            }
        }
    }

    int dfs(int s, int flow)
    {
        if (s == sink)
            return flow;

        for (int i = work[s]; i < adj[s].size(); i++, work[s]++)
        {
            auto &e = adj[s][i];

            if (depth[e.to] > depth[s] && e.cap - e.flow > 0)
            {
                int f = dfs(e.to, min(flow, e.cap - e.flow));

                if (f < 0)
                    continue;

                e.flow += f;
                adj[e.to][e.rev].flow -= f;

                return f;
            }
        }

        return -1;
    }

public:
    int source, sink;

    Dinic(int n)
    {
        source = 0;
        sink = n + 1;

        adj.resize(sink + 1);
        depth.resize(sink + 1);
        work.resize(sink + 1);
    }

    void add_edge(int u, int v, int cap)
    {
        adj[u].push_back(Edge(v, cap));
        adj[v].push_back(Edge(u, 0));
        adj[u].back().rev = adj[v].size() - 1;
        adj[v].back().rev = adj[u].size() - 1;
    }

    int max_flow()
    {
        int flow = 0;
        while (1)
        {
            bfs();
            if (depth[sink] == -1)
                break;

            fill(work.begin(), work.end(), 0);
            while (1)
            {
                int f = dfs(source, INF);
                if (f < 0)
                    break;
                flow += f;
            }
        }

        return flow;
    }

    void solve(int n)
    {
        max_flow();

        fill(depth.begin(), depth.end(), -1);

        vector<int> ans;
        queue<int> q;
        q.push(source);
        depth[source] = 0;

        while (!q.empty())
        {
            int s = q.front();
            q.pop();

            bool flag = true;
            for (auto &e : adj[s])
            {
                if (e.cap - e.flow > 0 && depth[e.to] == -1)
                {
                    depth[e.to] = depth[s] + 1;
                    q.push(e.to);
                    flag = false;
                }
            }

            if (flag && 1 <= s && s <= n)
            {
                bool flag2 = false;
                for (auto &e : adj[s])
                {
                    if (e.to == s + n && e.cap == e.flow)
                        flag2 = true;
                }
                if (flag2)
                    ans.push_back(s);
            }
        }

        sort(ans.begin(), ans.end());
        for (auto i : ans)
            cout << i << ' ';
    }
};

main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m, s, e;
    cin >> n >> m >> s >> e;

    Dinic MF(2 * n);
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        MF.add_edge(i, n + i, x);
    }

    MF.add_edge(MF.source, s, INF);
    MF.add_edge(n + e, MF.sink, INF);

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        MF.add_edge(n + a, b, INF);
        MF.add_edge(n + b, a, INF);
    }

    MF.solve(n);
}

ploffer11 4년 전 2

잘은 모르겠지만 solve가 약간 이상하게 돌아가는 모양입니다.

yungoon님의 도움으로 bfs 후 i는 갈 수 있는데 -> i+n은 못가는 경우를 찾아 출력했더니 바로 맞았습니다.

iknoom1107 2년 전 1

저도 정점 두개로 나누고(i 정점, i + n 정점)

위와 똑같이 bfs하면서 다음 방문할 정점이 없으면서 i 정점인지 체크하니까 틀리네요.

저도 bfs 후 i는 갈 수 있는데 -> i+n은 못가는 경우를 찾아 출력했더니 바로 맞았습니다.

이유를 한참동안 생각해봤는데 모르겠네요....

powergee 2년 전 7

2년전 글이지만 반례를 찾아서 댓글을 씁니다!

BFS를 모두 돌린 후에 정답의 후보를 판별하는 것이 아니라, BFS 도중에 후보를 판별하게 되면

입력으로 들어온 간선의 순서에 따라(즉, BFS하는 순서에 따라) 정답이 다르게 나올 수 있음을 발견하였습니다.

예를 들어, 아래 입력의 정답은 "3"입니다.

그리고 이 입력은 아래처럼 생겼습니다.

위 그림에서 알 수 있듯, 3만 막으면 5의 비용으로 끝낼 수 있으므로 "3"이 정답입니다.

그러나 제 제출(40353254), @iknoom1107 님의 제출(31031197), @ploffer11 님이 이 글에 쓰신 코드 모두 "3"을 출력하지 않고 있습니다.

그리고 간선의 입력 순서를 바꾸면 출력도 달라집니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

GG 반례를 못찾겠습니다

ploffer11 4년 전 3

ploffer11 4년 전 2

iknoom1107 2년 전 1

powergee 2년 전 7

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말