Submission #181456

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }


    void calc()
    {
        string[] st = splitLine(3, 3);
        int N = getInt(st[0], 1, 100);
        int G = getInt(st[1], 0, N - 1);
        int E = getInt(st[2], 0, N * (N - 1) / 2);
        int[] p = new int[G];
        
        st = splitLine(G, G);
        for (int i = 0; i < G; i++)
        {
            p[i] = getInt(st[i], 1, N - 1);
        }
        int[] a = new int[E];
        int[] b = new int[E];
        for (int i = 0; i < E; i++)
        {
            st = splitLine(2, 2);
            a[i] = getInt(st[0], 0, N - 1);
            b[i] = getInt(st[1], 0, N - 1);
            if (a[i] == b[i]) myon("!?");
        }

        V[] vs = new V[N];
        for (int i = 0; i < N; i++)
        {
            vs[i] = new V();
        }
        V goal = new V();

        for (int i = 0; i < E; i++)
        {
            vs[a[i]].add(vs[b[i]], 1);
        }

        for (int i = 0; i < G; i++)
        {
            vs[p[i]].add(goal, 1);
        }

        Console.WriteLine(dinic(vs[0], goal));

    }

    long INF = 1L << 62;
    long dinic(V s, V t)
    {
        long flow = 0;
        for (int p = 1; ; p++)
        {
            Queue<V> que = new Queue<V>();
            s.level = 0;
            s.p = p;
            que.Enqueue(s);
            while (que.Count != 0)
            {
                V v = que.Dequeue();
                v.iter = v.es.Count - 1;
                foreach (E e in v.es)
                {
                    if (e.to.p < p && e.cap > 0)
                    {
                        e.to.level = v.level + 1;
                        e.to.p = p;
                        que.Enqueue(e.to);
                    }
                }
            }
            if (t.p < p) return flow;
            for (long f = 0; (f = dfs(s, t, INF)) > 0; )
            {
                flow += f;
            }
        }
    }

    long dfs(V v, V t, long f)
    {
        if (v == t) return f;
        for (; v.iter >= 0; v.iter--)
        {
            E e = v.es[v.iter];
            if (v.level < e.to.level && e.cap > 0)
            {
                long d = dfs(e.to, t, Math.Min(f, e.cap));
                if (d > 0)
                {
                    e.cap -= d;
                    e.rev.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    class V
    {
        public V() { }
        public List<E> es = new List<E>();
        public int level, p, iter;
        public void add(V to, long cap)
        {
            E e = new E(to, cap);
            E rev = new E(this, cap);
            e.rev = rev;
            rev.rev = e;
            es.Add(e);
            to.es.Add(rev);
        }
    }

    class E
    {
        public V to;
        public E rev;
        public long cap;
        public E(V to, long cap)
        {
            this.to = to;
            this.cap = cap;
        }

    } 

    //swap
    void swap<T>(ref T a, ref T b)
    {
        T c = a;
        a = b;
        b = c;
    }

    void myon(string s)
    {
        throw new Exception(s);
    }

    int getInt(string s, int min, int max)
    {
        int ret = int.Parse(s);
        if (ret < min) throw new Exception("low");
        if (ret > max) throw new Exception("high");
        return ret;
    }

    int getIntLine(int min, int max)
    {
        int ret = int.Parse(Console.ReadLine());
        if (ret < min) throw new Exception("low");
        if (ret > max) throw new Exception("high");
        return ret;
    }

    double getDouble(string s, double min, double max)
    {
        double ret = double.Parse(s);
        if (ret < min) throw new Exception("low");
        if (ret > max) throw new Exception("high");
        return ret;
    }

    double getDoubleLine(double min, double max)
    {
        double ret = double.Parse(Console.ReadLine());
        if (ret < min) throw new Exception("low");
        if (ret > max) throw new Exception("high");
        return ret;
    }

    string getString(string s, int min, int max)
    {
        if (s.Length < min) throw new Exception("low");
        if (s.Length > max) throw new Exception("high");
        return s;
    }

    string getStringLine(int min, int max)
    {
        string s = Console.ReadLine();
        if (s.Length < min) throw new Exception("low");
        if (s.Length > max) throw new Exception("high");
        return s;
    }

    string[] splitLine(int min, int max)
    {
        string[] ret = Console.ReadLine().Split(' ');
        if (ret.Length == 1 && ret[0] == "") ret = new string[0];
        if (ret.Length < min || ret.Length > max) throw new Exception("wrong length");
        return ret;
    }
}

Submission Info

Judge Result