글 읽기 - 알고리즘 문제인가요 실수 처리 문제인가용.

sksdong1 7년 전 0

문제에서 모든 미션을 성공적으로 마쳐야 하기 때문에 0의 확률이 주어지는 간선은 제외하고,

모든 간선의 용량을 1로하고, 비용을 확률로 놓구 mcmf 돌렸는데요

미션 수 만큼 경로를 찾으면 종료했는데 머가 문제일까요.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

class Main{
	
	final int INF = 987654321,SOURCE=0,SINK=1;
	int n,MAX;
	int[][] cap,flow,cost;
	Scanner sc = new Scanner(System.in);
	void solve(){
		n = sc.nextInt();
		MAX = 2*n+2;
		
		cap = new int[MAX][MAX];
		flow = new int[MAX][MAX];
		cost = new int[MAX][MAX];
		
		for(int i=0;i<n;i++){
			cap[SOURCE][2+i]=1;
			cap[2+n+i][SINK]=1;
		}
		
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				int a = sc.nextInt();
				if(a==0) continue;
				cap[2+i][2+n+j]=1;
				cost[2+i][2+n+j]=-a;
				cost[2+n+j][2+i]=a;
			}
		}
		
		System.out.println(String.format("%6f", -mcmf()*100));
	}
	double mcmf(){
		int count=0;
		double total=1;
		LinkedList<Integer> q = new LinkedList<Integer>();
		double[] dist = new double[MAX];
		boolean[] chk = new boolean[MAX];
		int[] parent = new int[MAX];
		while(true){
			Arrays.fill(dist,INF);
			Arrays.fill(chk,false);
			Arrays.fill(parent,-1);
			q.clear();
			dist[SOURCE]=0;
			parent[SOURCE]=SOURCE;
			q.add(SOURCE);
			while(!q.isEmpty()){
				int here = q.poll();
				chk[here]=false;
				for(int i=0;i<MAX;i++){
					if(cap[here][i]-flow[here][i]>0 && dist[i]>dist[here]+cost[here][i]){
						dist[i]=dist[here]+cost[here][i];
						parent[i]=here;
						if(!chk[i]) q.add(i);
						chk[i]=true;
					}
				}
			}
			if(count==n) break;
			count++;
			total = total*(dist[SINK]/100);
			for(int p=SINK;p!=SOURCE;p=parent[p]){
				flow[parent[p]][p] +=1;
				flow[p][parent[p]] -=1;
			}
			
		}
		return total;
	}
	public static void main(String[] args) {
		new Main().solve();
	}
}

jjwdi0 7년 전 0

29번째 줄에 cost배열에 저장될 값이 -a이면 안 되지 않을까요??

double 형으로 선언해준 다음에 1/a를 cost로 두어야 할 것 같습니다.

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

문제

문제

출처

ICPC

알고리즘 문제인가요 실수 처리 문제인가용.

sksdong1 7년 전 0

jjwdi0 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말