Link: C. Anadi and Domino

C. Anadi and Domino

Description:
Anadi has a set of dominoes. Every domino has two parts, and each part contains some dots. For every a and b such that 1≤a≤b≤6, there is exactly one domino with a dots on one half and b dots on the other half. The set contains exactly 21 dominoes. Here is an exact illustration of his set:


Also, Anadi has an undirected graph without self-loops and multiple edges. He wants to choose some dominoes and place them on the edges of this graph. He can use at most one domino of each type. Each edge can fit at most one domino. It's not necessary to place a domino on each edge of the graph.

When placing a domino on an edge, he also chooses its direction. In other words, one half of any placed domino must be directed toward one of the endpoints of the edge and the other half must be directed toward the other endpoint. There's a catch: if there are multiple halves of dominoes directed toward the same vertex, each of these halves must contain the same number of dots.

How many dominoes at most can Anadi place on the edges of his graph?

Input
The first line contains two integers n and m (1≤n≤7, 0≤m≤n⋅(n−1)/2) — the number of vertices and the number of edges in the graph.

The next m lines contain two integers each. Integers in the i-th line are ai and bi (1≤a,b≤n, a≠b) and denote that there is an edge which connects vertices ai and bi.

The graph might be disconnected. It's however guaranteed that the graph doesn't contain any self-loops, and that there is at most one edge between any pair of vertices.

Output
Output one integer which denotes the maximum number of dominoes which Anadi can place on the edges of the graph.

Examples
input
4 4
1 2
2 3
3 4
4 1
output
4
input
7 0
output
0
input
3 1
1 3
output
1
input
7 21
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
output
16
Note
Here is an illustration of Anadi's graph from the first sample test:


And here is one of the ways to place a domino on each of its edges:

Note that each vertex is faced by the halves of dominoes with the same number of dots. For instance, all halves directed toward vertex 1 have three dots.

Problem solving:
这道题一开始我没读懂题意。
题意就是给了你总共有21张多米诺骨牌，每张牌有两个面，然后给你一个无向图，保证没有环和一个顶点多条边的情况存在。现在让你在这个图中的每个边放多米诺骨牌。有一个放置规则，问你最多能放几张多米诺骨牌上去。
放置规则就是，每个点的权值都是一样的，你在每条边上放的多米诺骨牌，因为它有两个面。需要保证两个面上面的大小就是它指向的点的权值。就比如说样例一的解释中顶点1，2，3，4，所对应的权值分别是3，1，6，3。并且每张牌只能用一次。

因为数据范围也很小，总共最多七个点，二十一条边，每个点的权值的情况只有六种（1，2，3，4，5，6）.我们可以暴力枚举每一种情况，用顶点的权值去推这条边能放的多米诺骨牌，进而推到每一条边，然后取所有情况中的最大值就是答案。

枚举的时候用到了dfs（这个是真的很巧，bly说这应该是基本操作的，我枯了。dfs的枚举应该就不用说了。具体的solving看代码注释吧。

Code:

#include <bits/stdc++.h>
using namespace std;
int Map[50][50], domin[50], n, m, a, b, ans;
/*因为数据范围很小，所以这里直接用二维数组存图了。domin数组表示当前节点枚举到的权值，50开的有点大了已经。不过问题不大*/
int check()
{
    set<pair<int, int> > se;//为了解决记录哪种牌有没有被用过的麻烦，我们直接把所有能放的牌都丢进这个set里面，最后set的size就是这种枚举情况下的最大值
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)//双重for循环对每两个顶点就行判断
            if (Map[i][j] && domin[i] <= domin[j])//如果这两个点是联通的并且i的权值小于等于j的权值（因为多米诺骨牌也是有方向的），说明这里是可以放一张牌的。
                se.insert(make_pair(domin[i], domin[j]));//满足情况的丢进set
    return se.size();//返回set的size，也就是这种情况下的答案。
}
void dfs(int x)//枚举每个点的权值的每种情况
{
    if (x == n + 1)//如果已经枚举了n个点，说明这一种枚举的情况已经结束了。
    {
        ans = max(ans, check());//每次对答案取一下最大值，保证算出来的是最多放置的多米诺骨牌数，check函数就是用来求当前所有顶点权值已知的情况下最多能放多少多米诺骨牌
        return;
    }
    for (int i = 1; i <= 6; i++)
    {
        domin[x] = i;//将当前这个顶点，六种情况分别列出来
        dfs(x + 1);//枚举下一个顶点
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        Map[a][b] = Map[b][a] = 1;//输入之后存图，注意是双向的，因为是无向图
    }
    dfs(1);//从第一个顶点开始枚举
    cout << ans << endl;
    return 0;
}

cf终于不是绿名了，虽然多少有点py的意思在里面。还是很知足的。下个目标->1500

赏