题意

https://vjudge.net/problem/CodeForces-1230C

给了你总共有21张多米诺骨牌，每张牌有两个面，然后给你一个无向图，保证没有环和一个顶点多条边的情况存在。现在让你在这个图中的每个边放多米诺骨牌。有一个放置规则，问你最多能放几张多米诺骨牌上去。放置规则就是，每个点的权值都是一样的，你在每条边上放的多米诺骨牌，因为它有两个面。需要保证两个面上面的大小就是它指向的点的权值。

如

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:

思路

建议直接看样例，题意就理解了。

当n<7时，显然所有边都能满足。

当n==7时，枚举两个点取值相同，然后求这两个点共同连的点数（不合法的情况），用m减去这个最小值即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=200005;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

int g[8][8];

int main()

{

    std::ios::sync_with_stdio(false);

    int n,m;

    cin>>n>>m;

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

    {

        int u,v;

        cin>>u>>v;

        g[u][v]=g[v][u]=1;

    }

    if(n<7)

    {

        cout<<m<<endl;

        return 0;

    }

    int mn=inf;

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

    {

        for(int j=i+1;j<=n;j++)

        {

            int t=0;

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

            {

                if(g[i][k]&&g[k][j])

                {

                    t++;

                }

            }

            mn=min(t,mn);

        }

    }

    cout<<m-mn<<endl;

    return 0;

}

巴特西

CodeForces - 1230C（思维/暴力）

题意

思路

代码

最新文章

热门文章