No.421 しろくろチョコレート yukicoder

No.421 しろくろチョコレート - yukicoder

問題概略

市松模様でサイズN*Mのチョコレートが渡される。

下記の方法でチョコレートを食べて、幸福度を最大にしたい。

２つの繋がったチョコレートを食べる　幸福度100

離れた２つの色違いのチョコレートを食べる　幸福度１０

チョコレートを一つ食べる　幸福度１

なお、渡されるチョコレートは虫食い状態である。

制約

$1\le N,M\le 50$
$S_i|=M$
$<span\; style="font-family:\; MathJax\_Math-italic;"><span\; style="font-size:\; 15.96px;">i</span></span><span\; style="font-family:\; \text{'}Helvetica\; Neue\text{'},\; Helvetica,\; Arial,\; sans-serif;"><span\; style="font-size:\; 14px;">+</span></span>\mathrm{<span\; style="font-family:\; \text{'}Helvetica\; Neue\text{'},\; Helvetica,\; Arial,\; sans-serif;"><span\; style="font-size:\; 14px;">j</span></span>}$ が偶数のとき、$S_{i,j}=$ 'w' または '.' 

$i+j$ が奇数のときSi,j=$S_{i,j}=$'b' または '.' 

解法　

なるべく繋げて食べて、残りを処理する問題になっている。

グリッドグラフの最大マッチング問題に帰着できる。

‪実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬

↑（参考） 

全部の頂点に番号をつけて、それを連結する感じでやってみた。

類題

C - 広告

@SuppressWarnings("unchecked")
public class Main
{
    static StringBuilder sb = new StringBuilder();
    static FastScanner sc = new FastScanner(System.in);
    static int INF = 1234567890;
    static long LINF = 123456789123456789L;
    static long MINF = -123456789123456789L;
    static long MOD = 1000000007;
    static int[] y8 = {0, 1, 0, -1, -1, 1, 1, -1};
    static int[] x8 = {1, 0, -1, 0, 1, -1, 1, -1};
    static long[] F;//factorial
    static boolean[] isPrime;
    static int[] primes;
    static char[][] map;

    static int H, W, K;
    static int[] A;

    public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        H = sc.nextInt();
        W = sc.nextInt();
        //0     ~    M-1
        //.  +M
        //M*(N-1)    M*N-1
        map = sc.nextCharArray2(H, W);
        edges = Stream.generate(ArrayList::new).limit(H * W + 2)
.toArray(ArrayList[]::new);
        //s N*M e N*M+1
        int s = H * W;
        int t = H * W + 1;
        int wcou = 0;
        int bcou = 0;
        used = new boolean[H * W + 2];
        for (int hi = 0; hi < H; hi++)
        {
            for (int wi = 0; wi < W; wi++)
            {
                if (map[hi][wi] == '.') continue;
                int nowId = getId(hi, wi);
                if ((hi + wi) % 2 == 0)
                {
                    addEdge(s, nowId, 1);
                    wcou++;
                }
                else
                {
                    addEdge(nowId, t, 1);
                    bcou++;
                    continue;
                }
                //シロなら　上下左右
                int rId = getrId(nowId);
                int lId = getlId(nowId);
                int uId = getuId(nowId);
                int dId = getdId(nowId);
                //r
                if (rId != -1 && getChar(rId) != '.')
                {
                    addEdge(nowId, rId, 1);
                }
                //l
                if (lId != -1 && getChar(lId) != '.')
                {
                    addEdge(nowId, lId, 1);
                }
                //u
                if (uId != -1 && getChar(uId) != '.')
                {
                    addEdge(nowId, uId, 1);
                }
                //d
                if (dId != -1 && getChar(dId) != '.')
                {
                    addEdge(nowId, dId, 1);
                }
            }
        }
        int match = fordFulkerson(s, t);
        int res = match * 100;
        wcou -= match;
        bcou -= match;
        res += Math.min(wcou, bcou) * 10;
        res += Math.abs(wcou - bcou);
        System.out.println(res);
    }

    static List<Edge>[] edges;
    static boolean[] used;

    public static char getChar(int id)
    {
        return map[id / W][id % W];
    }

    //範囲外なら-1
    public static int getId(int h, int w)
    {
        if (h < 0 || w < 0 || H <= h || W <= w) return -1;
        return h * W + w;
    }

public static int getX(int id)
    {
        return id % W;
    }

    public static int getY(int id)
    {
        return id / W;
    }

    //範囲外なら-1
    public static int getrId(int h, int w)
    {
        return getId(h, w + 1);
    }

    //範囲外なら-1
    public static int getrId(int id)
    {
        return getrId(getY(id), getX(id));
    }

    //範囲外なら-1
    public static int getlId(int h, int w)
    {
        return getId(h, w - 1);
    }

    //範囲外なら-1
    public static int getlId(int id)
    {
        return getlId(getY(id), getX(id));
    }

    //範囲外なら-1
    public static int getdId(int h, int w)
    {
        return getId(h + 1, w);
    }

    //範囲外なら-1
    public static int getdId(int id)
    {
        return getdId(getY(id), getX(id));
    }

    //範囲外なら-1
    public static int getuId(int h, int w)
    {
        return getId(h - 1, w);
    }

    //範囲外なら-1
    public static int getuId(int id)
    {
        return getuId(getY(id), getX(id));
    }


    public static int dfs(int now, int goal, int f)
    {
        if (now == goal)
        {
            return f;
        }
        used[now] = true;
        for (int i = 0; i < edges[now].size(); i++)
        {
            Edge e = edges[now].get(i);
            if (!used[e.to] && e.cap > 0)
            {
                int flow = dfs(e.to, goal, Math.min(f, e.cap));
                if (flow == 0) continue;
                e.cap -= flow;
                edges[e.to].get(e.rev).cap += flow;
                return flow;
            }
        }
        return 0;
    }

    public static int fordFulkerson(int s, int e)
    {
        int flow = 0;
        while (true)
        {
            Arrays.fill(used, false);
            int river = dfs(s, e, Integer.MAX_VALUE);
            if (river == 0) return flow;
            flow += river;
        }
    }

    public static void addEdge(int f, int t, int c)
    {
        edges[f].add(new Edge(t, c, edges[t].size()));
        edges[t].add(new Edge(f, 0, edges[f].size() - 1));
    }

    static class Edge
    {
        int to, cap, rev;

        Edge(int to, int cap, int rev)
        {
            this.to = to;
            this.cap = cap;
            this.rev = rev;
        }
    }