글 읽기 - 네트워크 플로우 문제인데 왜 틀렸는지 모르겠습니다...

qwerasdfzxcl 3년 전 1

푼 방식은 체스판 컬러링을 한 다음 soruce에서 검은색 점을 연결하고 하얀색 점에서 sink로 연결해준다음 검은색과 하얀색 점 사이를 인접한 점들끼리 연결해줘서 최대유량을 계산하는 방식으로 풀었습니다. 그런데 자꾸 틀렸다고 나오네요... 반례 찾아주시면 감사하겠습니다.

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
struct edge{
    int to, c, f;
    edge *rev;
    edge(){}
    edge(int _to, int _c){
        to=_to;
        c=_c;
        f=0;
        rev=nullptr;
    }
    int spare(){
        return c-f;
    }
    void addflow(int f1){
        f += f1;
        rev->f -= f1;
    }
};
int matrix[55][55], dx[4]={-1, 0, 0, 1}, dy[4]={0, -1, 1, 0};

void solve(){
    vector<edge*> adj[2526];
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=0;i<55;i++){
        for (int j=0;j<55;j++) matrix[i][j]=0;
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            scanf("%d", &matrix[i][j]);
        }
    }
    for (int i=1;i<=n*m;i++){
        if (((i-1)/m+(i-1)%m)%2){
            edge *e1=new edge(i, matrix[(i-1)/m+1][(i-1)%m+1]), *e2=new edge(0, 0);
            e1->rev=e2;
            e2->rev=e1;
            adj[0].push_back(e1);
            adj[i].push_back(e2);
        }
        else{
            edge *e1=new edge(2525, matrix[(i-1)/m+1][(i-1)%m+1]), *e2=new edge(i, 0);
            e1->rev=e2;
            e2->rev=e1;
            adj[i].push_back(e1);
            adj[2525].push_back(e2);
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            for (int k=0;k<4;k++){
                int tx=i+dx[k], ty=j+dy[k];
                if (tx==0 || tx==n+1 || ty==0 || ty==m+1) continue;
                if (!(tx<i || (tx==i && ty<j))) continue;
                edge *e1=new edge((tx-1)*m+ty, 1e9), *e2=new edge((i-1)*m+j, 1e9);
                if ((i-1)+(j-1)%2==1) e2->c=0;
                else e1->c=0;
                e1->rev=e2;
                e2->rev=e1;
                adj[(i-1)*m+j].push_back(e1);
                adj[(tx-1)*m+ty].push_back(e2);
            }
        }
    }
    ll ans=0;
    while(1){
        queue<int> q;
        q.push(0);
        int parent[2526];
        edge *path[2526]={0};
        fill(parent, parent+2526, -1);
        while(!q.empty() && parent[2525]==-1){
            int tmp=q.front();
            q.pop();
            for (edge *e:adj[tmp]){
                int v=e->to;
                if (e->spare()>0 && parent[v]==-1){
                    parent[v]=tmp;
                    path[v]=e;
                    q.push(v);
                    if (v==2525) break;
                }
            }
        }
        if (parent[2525]==-1) break;
        int tf=1e9;
        for (int i=2525;i!=0;i=parent[i]) tf=min(tf, path[i]->spare());
        for (int i=2525;i!=0;i=parent[i]) path[i]->addflow(tf);
        ans += tf;
    }
    ll ts=0;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) ts += matrix[i][j];
    }
    printf("%lld\n", ts-ans);
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}

qwerasdfzxcl 3년 전 0

해결했습니다. 60번째 줄 조건문에 괄호를 잘못 쳐서 틀렸네요... 이것땜에 몇 시간을 날린건지 ㅋㅋ

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

문제

문제

출처

ICPC

네트워크 플로우 문제인데 왜 틀렸는지 모르겠습니다...

qwerasdfzxcl 3년 전 1

qwerasdfzxcl 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말