글 읽기 - 90%에서 틀려용..

sksdong1 7년 전 0

알고리즘은 먼저 직원에서 일을 하나씩 할 수 있을 때의 매칭을 하구요 -> ans

매칭이 안된 일을 뽑아서 일에서 직원으로 매칭을하고 ->cnt

최대 매칭이 k를 넘으면 k까지만 해서 cnt = k

ans+cnt 하면 될거 같은데 90퍼에서 실패뜨네용..

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

class Main{

	static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>();
	static ArrayList<ArrayList<Integer>> adjb = new ArrayList<ArrayList<Integer>>();
	static int n,m,k;
	static boolean[] visit = new boolean[1001];
	static int[] bMatched = new int[1001];
	static int[] aMatched = new int[1001];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine().trim());

		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		for(int i=0;i<=1000;i++) adj.add(new ArrayList<Integer>());
		for(int i=0;i<=1000;i++) adjb.add(new ArrayList<Integer>());
		for(int i=1;i<=n;i++){
			st = new StringTokenizer(br.readLine().trim());
			int a = Integer.parseInt(st.nextToken());
			for(int j=0;j<a;j++){
				int b = Integer.parseInt(st.nextToken());
				adj.get(i).add(b);
				adjb.get(b).add(i);
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++){
			Arrays.fill(visit, false);
			if(DFS(i)) ans++;
		}
		
		ArrayList<Integer> picked = new ArrayList<Integer>();
		for(int i=1;i<=m;i++){
			if(bMatched[i]==0) picked.add(i); //매칭 안 된 일들만 pick
		}
		//역으로 일 -> 직원으로 매칭
		int cnt=0;
		for(int i=0;i<picked.size();i++){
			Arrays.fill(visit, false);
			if(DFS(picked.get(i),aMatched)) {
				cnt++;
			}
		}
		cnt =  cnt<=k?cnt:k; //매칭 개수 중 최대 k개 까지만 매칭가능
		System.out.println(ans+cnt);

	}
	static boolean DFS(int here){
		for(int i=0;i<adj.get(here).size();i++){
			int there = adj.get(here).get(i);
			if(visit[there]) continue;
			visit[there] = true;
			if(bMatched[there]==0 || DFS(bMatched[there])){
				bMatched[there]=here;
				return true;
			}
		}
		return false;
	}
	static boolean DFS(int here,int[] aMatched){
		for(int i=0;i<adjb.get(here).size();i++){
			int there = adjb.get(here).get(i);
			if(visit[there]) continue;
			visit[there] = true;
			if(aMatched[there]==0 || DFS(aMatched[there])){
				aMatched[there]=here;
				return true;
			}
		}
		return false;
	}
}

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

문제

문제

출처

ICPC

90%에서 틀려용..

sksdong1 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말