結果

問題 No.241 出席番号(1)
ユーザー uafr_cs
提出日時 2015-09-11 23:48:17
言語 Java
(openjdk 23)
結果
AC  
実行時間 139 ms / 2,000 ms
コード長 2,499 bytes
コンパイル時間 2,142 ms
コンパイル使用メモリ 78,776 KB
実行使用メモリ 41,936 KB
最終ジャッジ日時 2024-11-30 21:33:51
合計ジャッジ時間 7,227 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class Main {
    
public static final int INF = Integer.MAX_VALUE / 2 - 1;
    
    public static int dinic(Vertex s, Vertex t) {
        int flow = 0;
        for (int p = 1;; p++) {
            Queue<Vertex> que = new LinkedList<Vertex>();
            s.level = 0;
            s.p = p;
            que.offer(s);
            
            while (!que.isEmpty()) {
                Vertex v = que.poll();
                v.iter = v.es.size() - 1;
                for (Edge e : v.es)
                    if (e.to.p < p && e.cap > 0) {
                        e.to.level = v.level + 1;
                        e.to.p = p;
                        que.offer(e.to);
                    }
            }
            
            if (t.p < p){
                return flow;
            }
            
            for (int f; (f = dfs(s, t, INF)) > 0;){
                flow += f;
            }
        }
    }
    public static int dfs(Vertex v, Vertex t, int f) {
        if (v == t) {
            return f;
        }
        
        for (; v.iter >= 0; v.iter--) {
            Edge e = v.es.get(v.iter);
            if (v.level < e.to.level && e.cap > 0) {
                int d = dfs(e.to, t, Math.min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    e.rev.cap += d;
                    return d;
                }
            }
        }
        
        return 0;
    }
    public static class Vertex {
        ArrayList<Edge> es = new ArrayList<Edge>();
        int level, p, iter;
        int id;
        
        public Vertex(int id){ this.id = id; }
        void add(Vertex to, int cap) {
            Edge e = new Edge(to, cap), rev = new Edge(this, 0);
            e.rev = rev;
            rev.rev = e;
            es.add(e);
            to.es.add(rev);
        }
    }
    public static class Edge {
        Vertex to;
        Edge rev;
        int cap;
        Edge(Vertex to, int cap) {
            this.to = to;
            this.cap = cap;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        final int N = sc.nextInt();
        int[] number = new int[N];
        for(int i = 0; i < N; i++){
            number[i] = sc.nextInt();
        }
        
        Vertex s = new Vertex(-1);
        Vertex t = new Vertex(-1);
        
        Vertex[] from = new Vertex[N];
        Vertex[] to = new Vertex[N];
        for(int i = 0; i < N; i++){
            from[i] = new Vertex(i);
            to[i] = new Vertex(i);
        }
        
        for(int i = 0; i < N; i++){
            s.add(from[i], 1);
            to[i].add(t, 1);
        }
        
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(number[i] != j){
                    from[i].add(to[j], 1);
                }
            }
        }
        
        final int flow = dinic(s, t);
        
        if(flow < N){
            System.out.println(-1);
        }else{
            LOOP:
            for(int i = 0; i < N; i++){
                for(Edge e : from[i].es){
                    if(e.cap == 0){
                        System.out.println(e.to.id);
                        continue LOOP;
                    }
                }
            }
        }
        
        
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0