結果

問題 No.241 出席番号(1)
ユーザー kou6839kou6839
提出日時 2015-08-10 17:29:02
言語 Java21
(openjdk 21)
結果
AC  
実行時間 171 ms / 2,000 ms
コード長 1,991 bytes
コンパイル時間 2,316 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 42,504 KB
最終ジャッジ日時 2024-05-08 00:16:26
合計ジャッジ時間 7,978 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 114 ms
41,800 KB
testcase_01 AC 130 ms
41,232 KB
testcase_02 AC 121 ms
41,964 KB
testcase_03 AC 130 ms
41,240 KB
testcase_04 AC 139 ms
41,728 KB
testcase_05 AC 128 ms
41,328 KB
testcase_06 AC 127 ms
41,160 KB
testcase_07 AC 125 ms
41,420 KB
testcase_08 AC 126 ms
41,092 KB
testcase_09 AC 116 ms
41,496 KB
testcase_10 AC 123 ms
41,452 KB
testcase_11 AC 124 ms
41,400 KB
testcase_12 AC 125 ms
41,056 KB
testcase_13 AC 130 ms
41,296 KB
testcase_14 AC 168 ms
42,228 KB
testcase_15 AC 145 ms
42,080 KB
testcase_16 AC 117 ms
41,480 KB
testcase_17 AC 115 ms
41,396 KB
testcase_18 AC 126 ms
41,356 KB
testcase_19 AC 128 ms
41,876 KB
testcase_20 AC 125 ms
41,348 KB
testcase_21 AC 126 ms
41,328 KB
testcase_22 AC 127 ms
41,664 KB
testcase_23 AC 135 ms
41,456 KB
testcase_24 AC 148 ms
42,156 KB
testcase_25 AC 159 ms
42,264 KB
testcase_26 AC 171 ms
42,004 KB
testcase_27 AC 164 ms
42,416 KB
testcase_28 AC 160 ms
42,216 KB
testcase_29 AC 165 ms
42,252 KB
testcase_30 AC 165 ms
42,440 KB
testcase_31 AC 163 ms
42,504 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.nio.file.spi.FileSystemProvider;
import java.util.*;
import java.util.prefs.BackingStoreException;

import javax.swing.text.Highlighter.Highlight;

class MaximumFlow {
	public ArrayList<Edge>[] G;
	private boolean[] used;
	
	public class Edge{
		int to;
		int cap;
		int rev;
		
		public Edge(int to,int cap, int rev){
			this.to = to;
			this.cap = cap;
			this.rev = rev;
		}
	}
	
	public MaximumFlow(int v){
		used = new boolean[v];
		G = new ArrayList[v];
		for(int i=0;i<v;i++){
			G[i]=new ArrayList<>();
		}
	}	
	
	public void addEdge(int from,int to, int cap){
		G[from].add(new Edge(to, cap, G[to].size()));
		G[to].add(new Edge(from, 0, G[from].size()-1));
	}
	
	private int dfs(int v, int t, int f){
		if(v==t) return f;
		used[v]=true;
		for(int i=0;i<G[v].size();i++){
			Edge edge = G[v].get(i);
			
			if(!used[edge.to] && edge.cap>0){
				int d = dfs(edge.to,t,Math.min(f,edge.cap));
				
				if(d>0){
					edge.cap-=d;
					G[edge.to].get(edge.rev).cap += d;
					return d;
				}
			}
		}
		
		return 0;
	}
	
	public int maxFlow(int s,int t){
		int flow = 0;
		for(;;){
			Arrays.fill(used, false);
			int f = dfs(s, t, Integer.MAX_VALUE);
			
			if(f==0) return flow;
			flow+=f;
		}
	}
}
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] ng = new int[n];
		for(int i=0;i<n;i++) ng[i]=sc.nextInt();
		MaximumFlow mf = new MaximumFlow(2*n+2);
		for(int i=1;i<=n;i++){
			mf.addEdge(0, i, 1);
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(ng[i]!=j){
					mf.addEdge(i+1, j+n+1, 1);
				}
			}
		}
		for(int i=n+1;i<=2*n;i++){
			mf.addEdge(i, 2*n+1, 1);
		}
		int a = mf.maxFlow(0, 2*n+1);
		if(a != n ){
			System.out.println(-1);
		}else{
			t:for(int i=1;i<=n;i++){
				for(int j=0;j<mf.G[i].size();j++){
					if(mf.G[i].get(j).cap==0){
						System.out.println(mf.G[i].get(j).to-n-1);
						continue t;
					}
				}
			}
		}
		
	}
}
0