Submission #1416891

---

Source Code Expand

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Globalization;
using System.Diagnostics;



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

    Scanner cin;

    List<Tuple<int, int>>[] es;
    int[] loop;
    int[] memo;

    List<int> A;
    List<int> B;
    int[] Asum;
    int[] Bsum;

    void calc()
    {
        cin = new Scanner();
        int N = cin.nextInt();
        int M = cin.nextInt();
        int K = cin.nextInt();

        init(N);

        es = new List<Tuple<int, int>>[N];
        for (int i = 0; i < N; i++)
        {
            es[i] = new List<Tuple<int, int>>();
        }

        for (int i = 0; i < M; i++)
        {
            int f = cin.nextInt() - 1;
            int t = cin.nextInt() - 1;
            int c = cin.nextInt();
            es[f].Add(Tuple.Create(t, c));
            es[t].Add(Tuple.Create(f, c));
            connect(f, t);
        }
        loop = new int[N];
        memo = new int[N];
        findLoop(0, -1);

        A = new List<int>();
        B = new List<int>();
        for (int i = 0; i < N; i++)
        {
            foreach (var e in es[i])
            {
                int j = e.Item1;
                if (i > j) continue;
                if(loop[i] == 1 && loop[j] == 1)
                {
                    B.Add(e.Item2);
                }
                else
                {
                    A.Add(e.Item2);
                }
            }
        }

        A.Sort();
        B.Sort();
        Asum = new int[A.Count + 1];
        Bsum = new int[B.Count + 1];
        for (int i = 0; i < A.Count; i++)
        {
            Asum[i + 1] = Asum[i] + A[i];
        }
        for (int i = 0; i < B.Count; i++)
        {
            Bsum[i + 1] = Bsum[i] + B[i];
        }

        int cnt = 0;
        for (int i = 0; i < N; i++)
        {
            if (uni[i] < 0) cnt++;
        }
        int need = K - cnt;

        if (need < 0) need = 0;
        long ans = long.MaxValue / 2;
        if (A.Count >= need) ans = Asum[need];
        for (int i = 0; i <= need; i++)
        {
            int j = need - i + 1;
            if (Asum.Length <= i) continue;
            if (Bsum.Length <= j) continue;
            ans = Math.Min(Asum[i] + Bsum[j], ans);
        }
        Console.WriteLine(ans);


    }

    int[] uni;
    void init(int N)
    {
        uni = new int[N];
        for (int i = 0; i < N; i++)
        {
            uni[i] = -1;
        }
    }

    int root(int a)
    {
        if (uni[a] < 0) return a;
        else return uni[a] = root(uni[a]);
    }

    bool connect(int a, int b)
    {
        a = root(a);
        b = root(b);
        if (a == b) return false;
        if (uni[a] > uni[b]) swap(ref a, ref b);
        uni[a] += uni[b];
        uni[b] = a;
        return true;
    }

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

    int findLoop(int now, int pre)
    {
        if(memo[now] == 1)
        {
            loop[now] = 1;
            return 1;
        }
        memo[now] = 1;
        foreach (var e in es[now])
        {
            int next = e.Item1;
            if (next == pre) continue;
            int ans = findLoop(next, now);
            if(ans == 1)
            {
                if (loop[now] == 1) return 2;
                loop[now] = 1;
                return 1;
            }
            if (ans == 2) return 2;
        }
        memo[now] = 0;
        return 0;
    }

}


class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();

        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Submission Info

Judge Result