글 읽기 - 열혈강호1에서 source랑 사람 사이의 간선만 최대유량 2로 고쳤는데 틀리네요

dongwon0427 6년 전 0

31%에서 틀립니다..

똑같이 틀리셨던 분 계시면 저 좀 도와주세요..

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n,m,S,E;
vector<pii> A[2005];
int flow[2005][2005];
int work[2005];
int level[2005];
bool bfs() {
    for(int i=S;i<=E;i++) level[i]=-1;
    level[S]=0;
    queue<int> Q;
    int vt[2005]={0,};
    Q.push(S);
    while(!Q.empty()) {
        int idx = Q.front();
        Q.pop();
        for(int i=0;i<A[idx].size();i++) {
            if(level[A[idx][i].first] == -1 && A[idx][i].second - flow[idx][A[idx][i].first] > 0) {
                level[A[idx][i].first] = level[idx] + 1;
                Q.push(A[idx][i].first);
            }
        }
    }
    if(level[E]==-1) return false;
    return true;
}
int dfs(int idx,int f) {
    if(idx==E) return f;
    for(;work[idx]<A[idx].size();work[idx]++) {
        pii nxt = A[idx][work[idx]];
        if(level[idx]+1 == level[nxt.first] && nxt.second - flow[idx][nxt.first] > 0 ) {
            int tmp = dfs(nxt.first,min(f , nxt.second - flow[idx][nxt.first]));
            flow[idx][nxt.first] += tmp;
            flow[nxt.first][idx] -= tmp;
            if(tmp>0) return tmp;
        }
    }
    return 0;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    S=0, E=n+m+1;
    for(int i=1;i<=n;i++) {
        int g;
        cin>>g;
        for(int j=0;j<g;j++) {
            int tmp;
            cin>>tmp;
            tmp += n;
            A[i].push_back(pii(tmp,1));
            A[tmp].push_back(pii(i,1));
        }
    }
    for(int i=1;i<=n;i++) {
        A[S].push_back(pii(i,2));
        A[i].push_back(pii(S,2));
    }
    for(int i=n+1;i<=n+m;i++) {
        A[i].push_back(pii(E,1));
        A[E].push_back(pii(i,1));
    }

    while(bfs()) {
        for(int i=S;i<=E;i++) work[i]=0;
        while(1) {
            int tmp = dfs(S,5);
            if(tmp==0) break;
        }
    }
    int ans=0;
    for(int i=S;i<=E;i++) for(int j=E;j<=E;j++) {
        if(flow[i][j]==1) {
            ans++;
            //cout<<i<<' '<<j<<"\n";
        }
    }
    cout<<ans;
    return 0;
}

ainch96 6년 전 0

혹시 소스 보여주실 수 있나요?

ainch96 6년 전 0

저도 그렇게 해서 맞았거든요. 아마 사소한 실수가 있었을 것 같네요.

dongwon0427 6년 전 0

아 감사합니다

ainch96 6년 전 1

역방향 간선의 capacity를 0으로 해줘야 하는데 그 부분이 틀리셨네요. ( 혹시 모르시다면 플로우 취소를 위해서 역방향 간선의 capacity는 0이어야 합니다. )

그 부분을 고쳤더니 맞게 나옵니다. 아래 수정 코드입니다.

잉? 그런데 열형강호 1은 맞았다고요? 반례 데이터를 요구해야겠네요.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n,m,S,E;
vector<pii> A[2005];
int flow[2005][2005];
int work[2005];
int level[2005];
bool bfs() {
    for(int i=S;i<=E;i++) level[i]=-1;
    level[S]=0;
    queue<int> Q;
    int vt[2005]={0,};
    Q.push(S);
    while(!Q.empty()) {
        int idx = Q.front();
        Q.pop();
        for(int i=0;i<A[idx].size();i++) {
            if(level[A[idx][i].first] == -1 && A[idx][i].second - flow[idx][A[idx][i].first] > 0) {
                level[A[idx][i].first] = level[idx] + 1;
                Q.push(A[idx][i].first);
            }
        }
    }
    if(level[E]==-1) return false;
    return true;
}
int dfs(int idx,int f) {
    if(idx==E) return f;
    for(;work[idx]<A[idx].size();work[idx]++) {
        pii nxt = A[idx][work[idx]];
        if(level[idx]+1 == level[nxt.first] && nxt.second - flow[idx][nxt.first] > 0 ) {
            int tmp = dfs(nxt.first,min(f , nxt.second - flow[idx][nxt.first]));
            flow[idx][nxt.first] += tmp;
            flow[nxt.first][idx] -= tmp;
            if(tmp>0) return tmp;
        }
    }
    return 0;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    S=0, E=n+m+1;
    for(int i=1;i<=n;i++) {
        int g;
        cin>>g;
        for(int j=0;j<g;j++) {
            int tmp;
            cin>>tmp;
            tmp += n;
            A[i].push_back(pii(tmp,1));
            A[tmp].push_back(pii(i,0));
        }
    }
    for(int i=1;i<=n;i++) {
        A[S].push_back(pii(i,2));
        A[i].push_back(pii(S,0));
    }
    for(int i=n+1;i<=n+m;i++) {
        A[i].push_back(pii(E,1));
        A[E].push_back(pii(i,0));
    }
    int ans = 0;
    while(bfs()) {
        for(int i=S;i<=E;i++) work[i]=0;
        while(1) {
            int tmp = dfs(S,5);
            if(tmp==0) break;
            ans += tmp;
        }
    }
    cout<<ans;
    return 0;
}

ainch96 6년 전 1

요구(x) 요청(o)

dongwon0427 6년 전 0

아 제가 플로우를 제대로 모르고 있었네요 ㅠㅠ 감사드립니다

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

문제

문제

출처

ICPC

열혈강호1에서 source랑 사람 사이의 간선만 최대유량 2로 고쳤는데 틀리네요

dongwon0427 6년 전 0

ainch96 6년 전 0

ainch96 6년 전 0

dongwon0427 6년 전 0

ainch96 6년 전 1

ainch96 6년 전 1

dongwon0427 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말