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

Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) B. Bear and Three Musketeers | 书脊
http://codeforces.com/contest/574/problem/B

Do you know a story about the three musketeers? Anyway, you will learn about its origins now.

Richelimakieu is a cardinal in the city of Bearis. He is tired of dealing with crime by himself. He needs three brave warriors to help him to fight against bad guys.

There are n warriors. Richelimakieu wants to choose three of them to become musketeers but it's not that easy. The most important condition is that musketeers must know each other to cooperate efficiently. And they shouldn't be too well known because they could be betrayed by old friends. For each musketeer his recognition is the number of warriors he knows, excluding other two musketeers.

Help Richelimakieu! Find if it is possible to choose three musketeers knowing each other, and what is minimum possible sum of their recognitions.

题目大意: 给一个无向图, 问你是不是有三个点互联, 并且算出所有三点互联情况下, 这三点的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);

    }

Read full article from Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 2) B. Bear and Three Musketeers | 书脊