글 읽기 - 왜안되는걸까요...

smu201111192 7년 전 0

왜안되는걸까요..

source에서 모든음식에대한 용량을1, 음식에서 소까지 용량을1 소에서 음료에대한 용랑을1,모든 음료에서 sink까지 용량을 1로 설정한뒤

source에서 sink까지 maxflow를 구했는데 틀렸다고 나오네요.

예제케이스는 정답을 출력하는데 어디서 문제인지 잘모르겠습니다.

#include <iostream>
#include <queue>
using namespace std;
const int maxN=100;
int capacity[500][500]={0,};
int flow[500][500]={0,};
int N,F,D;
vector<vector<int> > adj;
void addEdge(int n,int m){
    capacity[n][m]=1;
    adj[n].push_back(m);
    adj[m].push_back(n);
}
int maxFlow(int src,int sink)
{
    int totalFlow=0;
    while(true){
        vector<int> parent(N+F+D+2,-1);
        queue<int> q;
        parent[src]=src;
        q.push(src);
        while(!q.empty()&&parent[sink]==-1){
            int here=q.front();
            q.pop();
            for(int i=0;i<adj[here].size();i++){
                int there=adj[here][i];
                if(parent[there]==-1 && capacity[here][there]-flow[here][there]>0)
                {
                    q.push(there);
                    parent[there]=here;
                }
            }
        }
        if(parent[sink]==-1)
            break;
        int cost=1e9+1;
        for(int i=sink;i!=src;i=parent[i]){
            cost=min(cost,capacity[parent[i]][i]-flow[parent[i]][i]);
        }
        
        for(int i=sink;i!=src;i=parent[i]){
            flow[parent[i]][i]+=cost;
            flow[i][parent[i]]-=cost;
        }
        totalFlow+=cost;
    }
    return totalFlow;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>N>>F>>D;
    adj.resize(N+F+D+2);
    int source=N+F+D;
    int sink=N+F+D+1;
    int food[maxN][maxN];
    int drink[maxN][maxN];
    for(int i=0;i<N;i++){
        int foodN,drinkN;
        cin>>foodN>>drinkN;
        for(int j=0;j<foodN;j++){
            cin>>food[i][j];
            addEdge(N+food[i][j]-1,i); //음식에서 i번째 소로
        }
        for(int k=0;k<drinkN;k++){
            cin>>drink[i][k];
            addEdge(i,N+F+drink[i][k]-1); //i번째소에서 음료로
        }
    }
    for(int i=0;i<F;i++){
        addEdge(N+F+D,N+i); //source에서 음식
    }
    for(int i=0;i<D;i++){
        addEdge(N+F+i,N+F+D+1); // 음료에서 sink
     }
    cout<<maxFlow(source,sink);
    return 0;
}

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

문제

문제

출처

ICPC

왜안되는걸까요...

smu201111192 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말