2014-team6/java

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== st0rm23 ===
{{{
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;


public class Main {
    int MAXN = 1000;
    int n, m;
    int[] fa, ma;
    int[][] vis;
    BigDecimal[][] ff;
    int[] dep;
    BigDecimal ans;
    BigDecimal fact;

    void init()
    {
        fa = new int[MAXN];
        Arrays.fill(fa, -1);
        ma = new int[MAXN];
        Arrays.fill(ma, -1);
        vis = new int[MAXN][MAXN];
        ff = new BigDecimal[MAXN][MAXN];
        dep = new int[MAXN];
        Arrays.fill(dep, -1);
        fact = BigDecimal.valueOf(0.5);
    }

    BigDecimal rp(int a, int b)
    {
        if (1 == vis[a][b]) return ff[a][b];
        if (a == b) return BigDecimal.valueOf(1);
        if (fa[a] == -1 && fa[b] == -1) return BigDecimal.valueOf(0);

        if (dep[a] > dep[b]) 
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
        BigDecimal tmp1 = rp(a, fa[b]);
        BigDecimal tmp2 = rp(a, ma[b]);
        tmp1 = tmp1.multiply(fact);
        tmp2 = tmp2.multiply(fact);
        BigDecimal ans = tmp1.add(tmp2);
        ff[a][b] = ans;
        ff[b][a] = ans;
        vis[a][b] = 1;
        vis[b][a] = 1;
        return ans;
    }

    void findDep(int i)
    {
        if (dep[i] != -1) return;
        if (fa[i] == -1)
        {
            dep[i] = 1;
            return;
        }
        findDep(fa[i]);
        findDep(ma[i]);
        if (dep[fa[i]] > dep[ma[i]]) dep[i] = dep[fa[i]] + 1;
        else dep[i] = dep[ma[i]] + 1;
    }

    void work()
    {
        boolean flag = false;
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext())
        {
            init();
            n = cin.nextInt();
            m = cin.nextInt();
            if (flag) System.out.println();
            for (int i=0; i<m; i++)
            {
                int a, b, c;
                a = cin.nextInt();
                b = cin.nextInt();
                c = cin.nextInt();
                fa[a] = b;
                ma[a] = c;
            }

            for (int i=1; i<=n; i++) findDep(i);

            int t;
            t = cin.nextInt();
            for (int i=0; i<t; i++)
            {
                int a, b;
                a = cin.nextInt();
                b = cin.nextInt();
                ans = rp(a, b);             



                String s = ans.movePointRight(2).toPlainString();
                if (s.indexOf('.') != -1) {
                int l = s.length() -1;
                while (s.charAt(l) == '0') 
                {
                    --l;
                }
                if (s.charAt(l) != '.') {
                    ++l;
                }
                s = s.substring(0, l);
                }
                System.out.print(s);
                System.out.println("%");
            }
            flag = true;
        }
    }

    public static void main(String args[])
    {
        //System.out.print("sb");
        Main main = new Main();
        main.work();
    }
}




}}}

st0rm23

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    int MAXN = 1000;
    int n, m;
    int[] fa, ma;
    int[][] vis;
    BigDecimal[][] ff;
    int[] dep;
    BigDecimal ans;
    BigDecimal fact;
    void init()
    {
        fa = new int[MAXN];
        Arrays.fill(fa, -1);
        ma = new int[MAXN];
        Arrays.fill(ma, -1);
        vis = new int[MAXN][MAXN];
        ff = new BigDecimal[MAXN][MAXN];
        dep = new int[MAXN];
        Arrays.fill(dep, -1);
        fact = BigDecimal.valueOf(0.5);
    }
    BigDecimal rp(int a, int b)
    {
        if (1 == vis[a][b]) return ff[a][b];
        if (a == b) return BigDecimal.valueOf(1);
        if (fa[a] == -1 && fa[b] == -1) return BigDecimal.valueOf(0);
        if (dep[a] > dep[b]) 
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
        BigDecimal tmp1 = rp(a, fa[b]);
        BigDecimal tmp2 = rp(a, ma[b]);
        tmp1 = tmp1.multiply(fact);
        tmp2 = tmp2.multiply(fact);
        BigDecimal ans = tmp1.add(tmp2);
        ff[a][b] = ans;
        ff[b][a] = ans;
        vis[a][b] = 1;
        vis[b][a] = 1;
        return ans;
    }
    void findDep(int i)
    {
        if (dep[i] != -1) return;
        if (fa[i] == -1)
        {
            dep[i] = 1;
            return;
        }
        findDep(fa[i]);
        findDep(ma[i]);
        if (dep[fa[i]] > dep[ma[i]]) dep[i] = dep[fa[i]] + 1;
        else dep[i] = dep[ma[i]] + 1;
    }
    void work()
    {
        boolean flag = false;
        Scanner cin = new Scanner(System.in);
        while (cin.hasNext())
        {
            init();
            n = cin.nextInt();
            m = cin.nextInt();
            if (flag) System.out.println();
            for (int i=0; i<m; i++)
            {
                int a, b, c;
                a = cin.nextInt();
                b = cin.nextInt();
                c = cin.nextInt();
                fa[a] = b;
                ma[a] = c;
            }
            for (int i=1; i<=n; i++) findDep(i);
            int t;
            t = cin.nextInt();
            for (int i=0; i<t; i++)
            {
                int a, b;
                a = cin.nextInt();
                b = cin.nextInt();
                ans = rp(a, b);             
                String s = ans.movePointRight(2).toPlainString();
                if (s.indexOf('.') != -1) {
                int l = s.length() -1;
                while (s.charAt(l) == '0') 
                {
                    --l;
                }
                if (s.charAt(l) != '.') {
                    ++l;
                }
                s = s.substring(0, l);
                }
                System.out.print(s);
                System.out.println("%");
            }
            flag = true;
        }
    }
    public static void main(String args[])
    {
        //System.out.print("sb");
        Main main = new Main();
        main.work();
    }
}