結果

問題 No.241 出席番号(1)
ユーザー kou6839
提出日時 2015-08-10 17:29:02
言語 Java
(openjdk 23)
結果
AC  
実行時間 153 ms / 2,000 ms
コード長 1,991 bytes
コンパイル時間 2,584 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 42,180 KB
最終ジャッジ日時 2024-11-30 21:32:15
合計ジャッジ時間 7,327 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

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;
                    }
                }
            }
        }
        
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0