Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) B. Bear and Three Musketeers

原题: http://codeforces.com/contest/574/problem/B

---

题目大意: 给一个无向图, 问你是不是有三个点互联, 并且算出所有三点互联情况下, 这三点的degree的合.

---

分析: 开始的时候, 看到4000的顶点数, 先想的就是直接暴, 后来发现第7个test case 过不了,  中间加了个简单的剪枝, 立刻就过了. 先把图建起来, 然后用个array存一下每个点的度, 最后用结果减去6(三个点互相连接的度), 就是这三点和其他点度的合.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.readInt();
        int m = in.readInt();
        int[] h = new int[n+1];
        boolean[][] g = new boolean[n+1][n+1];
        for (int i = 0; i < m; i++) {
            int x = in.readInt();
            int y = in.readInt();
            g[x][y] = true;
            g[y][x] = true;
            h[x]++;
            h[y]++;
        }
        int sum = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if(g[i][j]) {
                    for (int k = 1; k <= n; k++) {
                        if (g[j][k] && g[k][i]) {
                            sum = Math.min(sum, h[i] + h[j] + h[k]);
                        }
                    }
                }
            }
        }
        if (sum == Integer.MAX_VALUE)
            out.print(-1);
        else
            out.print(sum-6);
    }