3155267_ac_8391ms_5300k.java

北大大牛代码 1240道题的原代码 超级权威

import java.util.*;

public class Main
{
	
	public static void main(String [] args)
	{
		run();
	}
	
	static int tot;
	static Map <List<Integer>, Double> hash = new HashMap<List<Integer>, Double>();
	
	private static void run()
	{
		Scanner cin = new Scanner (System.in);
		int n, m;
		int u, v;
		
		n = cin.nextInt();
		m = cin.nextInt();
		tot = n * (n-1) / 2;
		int [] vest = new int [n];
		for(int i = 0; i < n; i++)
		{
			vest[i] = i;
		}
		for(int i = 0; i < m; i++)
		{
			u = cin.nextInt();
			v = cin.nextInt();
			u--;v--;
			for(int j = 0; j < n; j++)
			{
				if(j!=v&&vest[j]==vest[v])
				{
					vest[j] = vest[u];
				}
			}
			vest[v] = vest[u];
		}
		List <Integer> l = new ArrayList <Integer> ();
		boolean [] mark = new boolean [n];
		for(int i = 0; i < n; i++)
		{
			if(mark[i])
			{
				continue;
			}
			int no = 0;
			for(int j = 0; j < n; j++)
			{
				if(vest[j]==vest[i])
				{
					no++;
					mark[j] = true;
				}
			}
			if(no != 0)
			{
				l.add(no);
			}
		}
		List tmp = new ArrayList();
		tmp.add(n);
		hash.put(tmp, 0.0);
		System.out.println(expectation(l));
	}

	private static double expectation(List<Integer> l) 
	{
		Double ret;
		
		Collections.sort(l);
		if((ret = hash.get(l))!=null)
		{
			return ret;
		}
		int fail;
		int size = l.size();
		int [][] num = new int [size][size];
		for(int i = 0; i < size; i++)
		{
			for(int j = i+1; j < size; j++)
			{
				num[i][j] = l.get(i) * l.get(j);
			}
		}
		fail = 0;
		for(int i = 0; i < size; i++)
		{
			fail += l.get(i)*(l.get(i)-1)/2;
		}
		ret = 0.0;
		for(int i = 0; i < size; i++)
		{
			for(int j = i+1; j < size; j++)
			{
				List <Integer> tt = new ArrayList <Integer> (size - 1);
				tt.add(l.get(i)+l.get(j));
				for(int k = 0; k < size; k++)
				{
					if(k!=i&&k!=j)
					{
						tt.add(l.get(k));
					}
				}
				double p = num[i][j]*1.0/(tot-fail);
				double expe = num[i][j]*tot*1.0/((tot-fail)*(tot-fail));
				expe = expe + expectation(tt)*p;
				ret += expe;
			}
		}
		hash.put(l, ret);
		return ret;
	}
}