3541105_ac_844ms_4968k.java

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

import java.util.*;
import java.io.*;

public class Main {
	private Scanner in;
	private int n;
	private boolean [][] map;
	private int [][] flow;
	private final int INF = Integer.MAX_VALUE;

	public static void main(String [] args) {
		try {
			new Main().run();
		} catch (IOException ie) {
			while (true) {
				System.out.println("I love Shengqi");
			}
		}
	}

	private void run() throws IOException {
		in = new Scanner(System.in);
		//in = new Scanner(new FileInputStream("f.in"));
		String str;
		int u, v, m;

		while (in.hasNextInt()) {
			n = in.nextInt();
			m = in.nextInt();
			if (n <= 1) {
				System.out.println(n);
				continue;
			}
			map = new boolean [n][n];
			for (int i = 0; i < m; i++) {
				str = in.next();
				int index = str.indexOf(',');
				u = parseInt(str.substring(1, index));
				v = parseInt(str.substring(index + 1, str.length() - 1));
				if (u == v || map[u][v]) {
					m--;
					i--;
					continue;
				}
				map[u][v] = map[v][u] = true;
			}
			if (m < n - 1) {
				System.out.println("0");
				continue;
			}
			if (m == n * (n - 1) / 2) {
				System.out.println(n);
				continue;
			}
			System.out.println(pointConnectivity());
		}
	}

	private int parseInt(String str) {
		return Integer.parseInt(str);
	}

	private void createGraph(int s, int t) {
		flow = new int [n * 2][n * 2];
		for (int i = 0; i < n; i++) {
			flow[i][i + n] = 1;
			for (int j = 0; j < n; j++) {
				if (map[i][j]) {
					flow[i + n][j] = INF;
				}
			}
		}
		flow[s][s + n] = INF;
		flow[t][t + n] = INF;
	}

	private void show() {
		System.out.println("begin");
		for (int i = 0; i < n * 2; i++) {
			for (int j = 0; j < n * 2; j++) {
				if (flow[i][j] == INF) {
					System.out.print(2 + " ");
				} else {
					System.out.print(flow[i][j] + " ");
				}
			}
			System.out.println();
		}
		System.out.println("done");
	}

	private int bfs(int s, int t) {
		boolean mark = false;
		int f, r, p, C;
		int [] pre = new int [100];
		boolean [] visited = new boolean [100];
		int [] queue = new int [100];
		int [] F = new int [100];

		//System.out.println(s + " " + t);
		//show();
		f = r = -1;
		Arrays.fill(pre, 0);
		Arrays.fill(visited, false);
		visited[s] = true;queue[++f] = s;pre[s] = -1;
		C = INF;
		loop: 
		while(f != r) {
			++r;
			p = queue[r];
			for(int i = 0; i < n * 2; i++) {
				if(flow[p][i] != 0 && !visited[i]) {
					visited[i] = true;
					queue[++f] = i;
					pre[i] = p;
					F[i] = flow[p][i];
					if(i == t) {	
						mark = true;
						break loop;
					}
				}
			}
		}
		//System.out.println("mark is " + mark);
		if(mark) {
			p = t;
			while(pre[p] != -1) {
				if(F[p]<C)
					C = F[p];
				p = pre[p];
			}
			p = t;
			while(pre[p]!=-1) {
				flow[pre[p]][p] -= C;
				flow[p][pre[p]] += C;
				p = pre[p];
			}
			return C;
		}
		return 0;
	}

	private int maxFlow(int s, int t) {
		int maxflow = 0, f;

		while ((f = bfs(s, t)) != 0) {
			maxflow += f;
		}
		return maxflow;
	}

	private int pointConnectivity() {
		int ret = n;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j || map[i][j]) {
					continue;
				}
				createGraph(i, j);
				ret = Math.min(ret, maxFlow(i, j + n));
			}
		}
		return ret;
	}
}