結果

問題 No.421 しろくろチョコレート
ユーザー kuuso1
提出日時 2016-09-10 15:53:45
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 38 ms / 2,000 ms
コード長 3,301 bytes
コンパイル時間 1,030 ms
コンパイル使用メモリ 113,040 KB
実行使用メモリ 26,172 KB
最終ジャッジ日時 2024-09-23 07:08:29
合計ジャッジ時間 4,423 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

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

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class TEST{
    static void Main(){
        Sol mySol =new Sol();
        mySol.Solve();
    }
}
class Sol{
    public void Solve(){
        
        int V = N*M+2;
        int src = N*M;
        int sink = src+1;
        var Gr = new MaxFlow_Dinic();
        Gr.Init(V);
        int b = 0;
        int w = 0;
        
        int[] dx = new int[]{1,0,-1,0};
        int[] dy = new int[]{0,-1,0,1};
        Func<int,int,bool> InRange = (y,x) =>{
            return 0<= x && x < M && 0<= y && y < N;
        };
        
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(S[i][j] == 'b'){
                    b++;
                    Gr.AddEdge(src,i*M+j,1);
                    for(int t=0;t<4;t++){
                        int nx = j + dx[t];
                        int ny = i + dy[t];
                        if(!InRange(ny,nx))continue;
                        if(S[ny][nx] == 'w'){
                            Gr.AddEdge(i*M+j,ny*M+nx,1);
                        }
                    }
                }
                if(S[i][j] == 'w'){
                    w++;
                    Gr.AddEdge(i*M+j,sink,1);
                }
            }
        }
        int bw = Gr.MaxFlow(src,sink);
        int ans = bw * 100;
        b -= bw;
        w -= bw;
        int bws = Math.Min(b,w);
        ans += bws * 10;
        b -= bws;
        w -= bws;
        ans += b;
        ans += w;
        
        Console.WriteLine(ans);
        
        
        
        
    }
    int N,M;
    String[] S;
    public Sol(){
        var d = ria();
        N = d[0];
        M = d[1];
        S = new String[N];
        for(int i=0;i<N;i++)S[i] = rs();
    }
    static String rs(){return Console.ReadLine();}
    static int ri(){return int.Parse(Console.ReadLine());}
    static long rl(){return long.Parse(Console.ReadLine());}
    static double rd(){return double.Parse(Console.ReadLine());}
    static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
    static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
    static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
    static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}
class MaxFlow_Dinic{
    // arihon is god
    class Edge {
        public int To,Cap,Rev;
        public Edge(int to = 0,int cap = 0,int rev = 0){
            To = to;
            Cap = cap;
            Rev = rev;
        }
    }
    
    List<Edge>[] G;
    int[] Level;
    int[] Iter;
    
    static int Inf = (int) 1e9;
    public int N;
    public void Init(int n){
        N = n;
        G = new List<Edge>[N];
        for(int i=0;i<N;i++) G[i] = new List<Edge>();
        Level = new int[N];
        Iter = new int[N];
    }
    
    
    public void AddEdge(int from, int to, int cap){
        G[from].Add(new Edge(to,cap,G[to].Count));
        G[to].Add(new Edge(from,0,G[from].Count-1));
    }
    
    void bfs(int s){
        for(int j=0;j<G.Length;j++)Level[j] = -1;
        var Q = new Queue<int>();
        Level[s] = 0;
        Q.Enqueue(s);
        
        while(Q.Count>0){
            var v = Q.Dequeue();
            foreach(var e in G[v]){
                if(e.Cap > 0 && Level[e.To] < 0){
                    Level[e.To] = Level[v] + 1;
                    Q.Enqueue(e.To);
                }
            }
        }
    }
    
    int dfs(int v, int t, int f){
        if(v == t) return f;
        for(;Iter[v] < G[v].Count; Iter[v]++){
            var e = G[v][Iter[v]];
            if(e.Cap > 0 && Level[v] < Level[e.To]){
                int d = dfs(e.To, t, Math.Min(f,e.Cap));
                if(d > 0){
                    e.Cap -= d;
                    G[e.To][e.Rev].Cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    
    public int MaxFlow(int s, int t){
        int flow = 0;
        while(true){
            bfs(s);
            if(Level[t] < 0) return flow;
            Iter = new int[N];
            int f;
            while( ( f = dfs(s,t,Inf)) > 0){
                flow += f;
            }
        }
    }
    
    
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0