2013
11-12

# Interconnect

There are two serious problems in the Kingdom of Lipshire: the roads and the fools who build them. Once upon a time, the King of Lipshire has decided to improve the road system because some roads became completely impassable — it was easier to travel cross-country instead of using those roads.

By King’s decree, new roads are to be built in Lipshire. Of course, the new road system must interconnect all towns, i. e. there must be a path connecting any two towns of Lipshire.

The road administration of Lipshire has resources to build exactly one road per year. Unfortunately, the fools who build these roads are completely out of control. So, regardless of the orders given, the fools randomly select two different towns a and b and build a road between them, even when those towns are already connected by a road. All possible choices are equiprobable. The road is build in such a manner that the only points where a traveler can leave it are the towns connected by this road. The only good thing is that all roads are bidirectional.

The King knows about the problem, but he cannot do anything about it. The only thing King needs to know is the expected number of years to wait before the road system of Lipshire becomes interconnected. He asked you to provide this information.

The first line of the input contains two integers n and m (2 ≤ n ≤ 30, 0 ≤ m ≤ 1 000) — the number of towns in Lipshire, and the number of roads which are still good. The following m lines describe roads, one per line. Each road is described with two endpoints — two integer numbers ui and vi (1 ≤ ui, vin, uivi). There can be multiple roads between two towns, but the road from a town to itself is not allowed.

Output the expected number of years to wait for the interconnected road system. If the system is already interconnected, output zero as an answer. Output the number with at least six precise digits after the decimal point.

sample input #1
2 1
1 2

sample input #2
4 2
1 2
3 4

sample output #1
0.0

sample output #2
1.5

//* @author:
import java.util.*;
import java.io.File;
import java.io.PrintWriter;
import java.io.FileNotFoundException;

public class Main {

private static int nn;

public static void main(String[] args) throws FileNotFoundException {
//  Scanner in = new Scanner(new File("in"));
Scanner in=new Scanner(System.in);
//  PrintWriter out = new PrintWriter("ans.out");
int n = in.nextInt();
nn = (n * (n - 1)) / 2;
int m = in.nextInt();
int[] p = new int[n];
for (int i = 0; i < n; i++) p[i] = i;
for (int i = 0; i < m; i++) {
int u = in.nextInt();
int v = in.nextInt();
u--;
v--;
int k = p[u];
for (int j = 0; j < n; j++) {
if (p[j] == k) {
p[j] = p[v];
}
}
}
List< Integer> st = new ArrayList< Integer>();
for (int i = 0; i < n; i++) {
int s = 0;
for (int j = 0; j < n; j++) {
if (p[j] == i) s++;
}
if (s > 0) {
st.add(s);
}
}
Collections.sort(st);
List< Integer> fn = new ArrayList< Integer>();
fn.add(n);
mem.put(fn, 0.0);
System.out.println(get(st));
//   System.out.println(mem.size());
// System.out.close();
}

static Map< List< Integer>, Double> mem = new HashMap< List< Integer>, Double>();

private static double get(List< Integer> st) {
Double ret = mem.get(st);
if (ret != null) return ret;
int m = st.size();
int[][] a = new int[m][m];
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
a[i][j] = st.get(i) * st.get(j);
}
}
int s = 0;
for (int i = 0; i < m; i++) {
s += st.get(i) * (st.get(i) - 1) / 2;
}
double res = 0;
for (int i = 0; i < m; i++) {
for (int j = i + 1; j < m; j++) {
List< Integer> ss = new ArrayList< Integer>(st.size() - 1);
boolean q = true;
int z = st.get(i) + st.get(j);
for (int k = 0; k < m; k++) {
if (k != i && k != j) {
int zz = st.get(k);
if (q && zz >= z) {
q = false;
ss.add(z);
}
ss.add(zz);
}
}
if (q)
ss.add(z);
double p = a[i][j] * 1.0 / (nn - s);
double e = a[i][j] * 1.0 / ((1 - s * 1.0 / nn) * (1 - s * 1.0 / nn) * nn);
e = e + get(ss) * p;
res += e;
}
}
//  System.out.println(st);
mem.put(st, res);
return res;
}

}

1. 这道题目虽然简单，但是小编做的很到位，应该会给很多人启发吧！对于面试当中不给开辟额外空间的问题不是绝对的，实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟，今天看到小编这篇文章相见恨晚。