글 읽기 - 이분 매칭이 아닌 에드먼드 카프 알고리즘을 쓸 수는 없나요?

jaeminkim408 4년 전 0

문제가 이분 매칭 관련 내용이라는 것은 알고 있지만, 에드먼드 카프 알고리즘을 사용하고 싶었습니다.

그래서 그에 따라서 Queue를 사용한 BFS를 설정하고 코드를 작성했는데 어느 부분에서 틀렸는지 모르겠습니다.

혹시 어느 부분에서 틀린 건지 알려주실 수 있으실까요? 감사합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

import java.util.Queue;
import java.util.LinkedList;
import java.util.Arrays;
import java.util.ArrayList;

class Edge{
	int to, cap, flow;
	Edge reverse;
	Edge(int i_to, int i_cap, int i_flow, Edge i_rev){
		this.to=i_to;
		this.cap=i_cap;
		this.flow=i_flow;
		this.reverse=i_rev;
	}
	Edge(int i_to, int i_cap){
		this.to=i_to;
		this.cap=i_cap;
		this.flow=0;
		this.reverse=null;
	}
	
	Edge(){
		this(0,0,0,null);
	}
	
	int residue() {
		return this.cap-this.flow;
	}
	
	void addFlow(int a) {
		this.flow+=a;
		this.reverse.flow-=a;
	}
}

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int m=Integer.parseInt(st.nextToken());
		ArrayList[] adj= new ArrayList[n+m+2];
		for(int i=0;i<n+m+2;i++) {adj[i]=new ArrayList<Edge>();}
		
		for(int i=1;i<=n;i++) {
			st=new StringTokenizer(br.readLine());
			int k=Integer.parseInt(st.nextToken());
			Edge link_start=new Edge(i, 1);
			Edge link_start_rev=new Edge(0, 1,1,null);
			link_start.reverse=link_start_rev;
			link_start_rev.reverse=link_start;
			
			Edge link_end=new Edge(n+m+1, 1);
			Edge link_end_rev=new Edge(n+i,1,1,null);
			link_end.reverse=link_end_rev;
			link_end_rev.reverse=link_end;
			
			
			for(int j=0;j<k;j++) {
				int to=Integer.parseInt(st.nextToken())+n;
				Edge e1=new Edge(to,1);
				Edge e2=new Edge(i,1,1,null);
				e1.reverse=e2;
				e2.reverse=e1;
				adj[i].add(e1);
				adj[to].add(e2);
			}
			
			adj[0].add(link_start);
			adj[i].add(link_start_rev);
			
			adj[n+i].add(link_end);
			adj[n+m+1].add(link_end_rev);
		}
		
		int start=0;
		int end=n+m+1;
		int ans=0;
		
		while(true) {
			int[] prev=new int[n+m+2];
			Edge[] path=new Edge[n+m+2];
			Arrays.fill(prev, -1);
			Queue<Integer> q=new LinkedList<Integer>();
			q.clear();
			q.add(start);
			while(!q.isEmpty() && prev[end]==-1) {
				int curr=q.poll();
				for(int i=0;i<adj[curr].size();i++) {
					Edge next_edge=(Edge)adj[curr].get(i);
					int next=next_edge.to;
					if((next_edge.residue()>0) && prev[next]==-1) {
						q.add(next);
						prev[next]=curr;
						path[next]=next_edge;
						if(next==end) {break;}
					}
				}
			}
			
			if(prev[end]==-1) {break;}
			for(int i=end;i!=start;i=prev[i]) {
				path[i].addFlow(1);
			}

			ans++;
		}
		
		System.out.print(ans);
	}
}

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

문제

문제

출처

ICPC

이분 매칭이 아닌 에드먼드 카프 알고리즘을 쓸 수는 없나요?

jaeminkim408 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말