Anadi and Domino

参考：Anadi and Domino

思路：分为两种情况：

①n<=6，这个时候肯定可以保证降所有的边都放上一张多米诺牌，那么答案就是m

②n==7，在这种情况下肯定会出现某两个点a和b是靠一张两端同点数的多米诺牌连接起来的，而这个时候如果又有一个点同时与这两个点a和b都有一条边，那么，只能够在其中一条边上放多米诺牌，而另外一边不可以。那么我们就可以将它分成两部分，一个是连接a的边，一个是连接b的边，那么为了连接更多的边，那么我们只需要得出我们最少的不能够连接的边即可。

那么我们用二重循环遍历7个点的组合，得到最少的不能够连接的边cnt，然后ans=m-cnt

代码：

// Created by CAD on 2019/9/25.

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

#define test(n) cout<<n<<endl

using namespace std;

int G[10][10];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    int n,m;    cin>>n>>m;

    for(int i=1,u,v;i<=m;++i)

        cin>>u>>v,G[u][v]=G[v][u]=1;

    if(n<=6)

        test(m);

    else

    {

        int cnt=inf;

        for(int i=1;i<=7;++i)

            for(int j=1;j<=7&&i!=j;++j)

            {

                int temp=0;

                for(int k=1;k<=7;++k)

                    if(G[i][k]&&G[j][k]) temp++;

                cnt=min(cnt,temp);

            }

        cout<<m-cnt<<endl;

    }

    return 0;

}

巴特西

Anadi and Domino

最新文章

热门文章