Submission #19529

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		String[] nmk = s.readLine().split(" ");
		int N = Integer.valueOf(nmk[0]);
		int M = Integer.valueOf(nmk[1]);
		int K = Integer.valueOf(nmk[2]);
		boolean[][] forbidden = new boolean[N][N];
		for (int i = 0 ; i < M ; i++) {
			String[] data = s.readLine().split(" ");
			int a = Integer.valueOf(data[0]);
			int b = Integer.valueOf(data[1]);
			forbidden[a][b] = true;
			forbidden[b][a] = true;
		}

		long till = System.currentTimeMillis() + 9000;
		long succeeded = 0;
		long tried = 0;
		
		int[] init = new int[N];
		for (int i = 0 ; i < N ; i++) {
			init[i] = i;
		}
		while (true) {
			int[] now = init.clone();
			if (tried % 100 == 0) {
				if (System.currentTimeMillis() >= till) {
					break;
				}
			}
			for (int k = 0 ; k < K ; k++) {
				int a = (int)(Math.random() * N);
				int b = (int)(Math.random() * N);
				if (a == b) {
					k--;
					continue;
				}
				int t = now[a];
				now[a] = now[b];
				now[b] = t;
			}
			
			tried++;
			if (!forbidden[now[0]][now[N-1]]) {
				boolean isok = true;
				for (int i = 0 ; i < N - 1 ; i++) {
					if (forbidden[now[i]][now[i+1]]) {
						isok = false;
						break;
					}
				}
				if (isok) {
					succeeded++;
				}
			}
		}
		System.out.println(1.0d * succeeded / tried);
	}
}

Submission Info

Judge Result