結果

問題 No.519 アイドルユニット
コンテスト
ユーザー uafr_cs
提出日時 2017-11-08 15:21:33
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,600 bytes
コンパイル時間 2,968 ms
コンパイル使用メモリ 80,184 KB
実行使用メモリ 93,824 KB
最終ジャッジ日時 2024-11-24 05:56:36
合計ジャッジ時間 46,592 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15 TLE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	public static class Edge implements Comparable<Edge> {
		int from, to, cost;
		
		public Edge(int from, int to, int cost){
			this.from = from;
			this.to = to;
			this.cost = cost;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.cost, o.cost);
		}
	}
	
	public static int answer = Integer.MAX_VALUE;
	
	public static void rec(int[] match, int prev, int matched, int n, ArrayList<ArrayList<Edge>> adj, int opt){
		if(opt >= answer){ return; }
		//System.out.println(answer);
		
		int from = prev + 1;
		while(from < n && match[from] >= 0){ from++; }
		//System.out.println(from);
		
		for(final Edge edge : adj.get(from)){
			final int to = edge.to;
			if(match[to] >= 0){ continue; }
			
			final int next_opt = opt + edge.cost;
			final int next_matched = matched + 2;
			
			match[to] = from; match[from] = 	to;
			
			if(next_matched < n){ rec(match, from, next_matched, n, adj, next_opt); }
			else{ answer = Math.min(answer, next_opt); }
			
			match[to] = match[from] = -1;
		}
	}
	
	public static int solve_dfs(int n, int[][] adj){		
		ArrayList<ArrayList<Edge>> sorted = new ArrayList<ArrayList<Edge>>();
		
		for(int i = 0; i < n; i++){
			ArrayList<Edge> inner = new ArrayList<Edge>();
			
			for(int j = i + 1; j < n; j++){ inner.add(new Edge(i, j, adj[i][j])); }
			
			Collections.sort(inner);
			sorted.add(inner);
		}
		
		int[] match = new int[n];
		Arrays.fill(match, -1);
		
		rec(match, -1, 0, n, sorted, 0);
		return answer;
	}
	
	public static int solve_DP(int n, int[][] adj){
		int[] DP = new int[1 << n];
		Arrays.fill(DP, Integer.MAX_VALUE / 2 - 1);
		DP[0] = 0;
		
		for(int bit = 0; bit < (1 << n); bit++){
			//System.out.println(bit);
			int i = 0;
			for (; (bit & (1 << i)) != 0; ++i);
			
			final int fst = 1 << i;
			for(int j = i + 1; j < n; j++){
				final int snd = 1 << j;
				
				final int next_bit = bit | fst | snd;
				DP[next_bit] = Math.min(DP[next_bit], DP[bit] + adj[i][j]);
			}
		}
		
		return DP[(1 << n) - 1];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		final int n = sc.nextInt();
		
		final int max = 1000;
		int[][] adj = new int[n][n];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				adj[i][j] = max - sc.nextInt();
			}
		}
		
		//final int solve = solve_DP(n, adj);
		final int solve = solve_dfs(n, adj);
		
		System.out.println(max * (n / 2) - solve);
	}
}
0