글 읽기 - 열혈강호 문제 왜틀린지 모르겠습니다. 도와주세요 ㅠ

smu201111192 6년 전 0

예제 테스트케이스는 되는데 어디서 안되는지 잘모르겟네요.

이문제 푸신분계시면 좀도와주세요 ㅠㅠ

#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
struct edge{
    int to,cap,rev;
    edge(int to,int cap,int rev){
        this->to=to;
        this->cap=cap;
        this->rev=rev;
    }
    edge(){}
};
vector<vector<edge> > adj;
int n,m,k,source,sink,mid;
const int MAX=5005;
int level[MAX];
int iter[MAX];
void bfs(int s){
    memset(level,-1,sizeof(level));
    level[s]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int here=q.front();
        q.pop();
        for(int i=0;i<adj[here].size();i++){
            edge e=adj[here][i];
            if(e.cap>0 && level[e.to]==-1)
            {
                level[e.to]=level[here]+1;
                q.push(e.to);
            }
        }
    }
}
int dfs(int here,int t,int f){
    if(t==here)
        return f;
    for(int &i=iter[here];i<adj[here].size();i++){
        edge &e=adj[here][i];
        if(e.cap>0 &&level[e.to]>level[here]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                adj[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int maxFlow(int source,int sink){
    int mx=0;
    while(true){
        bfs(source);
        if(level[sink]==-1)
            return mx;
        int t=1;
        memset(iter,0,sizeof(iter));
        while(t>0){
            t=dfs(source,sink,1e9+1);
            mx+=t;
        }
    }
}
int getWork(int num){
    return num+m;
}
int getPerson(int num){
    return num;
}
void addEdge(int from,int to,int cap){
    adj[from].push_back(edge(to,cap,(int)adj[to].size()));
    adj[to].push_back(edge(from,0,(int)adj[from].size()-1));
}

int main(){
    scanf("%d %d %d",&n,&m,&k);
    adj.resize(5000);
    source=0,sink=n+m+1;
    mid=sink+1;
    int person[MAX]={0,};
    for(int i=1;i<=n;i++){
        int pN;scanf("%d",&pN);
        person[i]=pN;
        for(int j=0;j<pN;j++){
            int w;scanf("%d",&w);
            addEdge(getPerson(i),getWork(w),1); //각사람에서 할수잇는 일로 edge연결 capacity 1
        }
    }
    addEdge(source,mid,n+k); //source->mid 까지 capacity n+k(사람수+벌점수)
    for(int i=1;i<=n;i++){
        addEdge(mid,getPerson(i),k);  //mid에서 각사람으로 capacity k
    }
     for(int i=1;i<=n;i++){
        addEdge(mid,getPerson(i),1); //mid에서 각사람으로 capacity 1
    }
    for(int i=1;i<=m;i++){
        addEdge(getWork(i),sink,1);  //각work에서->sink로 capacity 1
    }
    printf("%d",maxFlow(source,sink));  //max 플로우를 구함
    return 0;
}


/*
3 8 3
3 1 6 5
4 5 6 7 8
1 5

*/

isac322 6년 전 1

저도 맨첨에 그렇게 생각했는데 WA네요ㅠㅠ

혹시나 해서 열혈강호 3처럼 해봤습니다.

exqt님의 댓글과 비스한데, 파란색 간선들에 각각 가중치를 1대신 k로 주고 푸니 AC떴습니다.

댓글처럼 반례가 뭔지 잘 모르겠는데 이게 맞는 것 같네요...

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

문제

문제

출처

ICPC

열혈강호 문제 왜틀린지 모르겠습니다. 도와주세요 ㅠ

smu201111192 6년 전 0

isac322 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말