C. Anadi and Domino

题目链接：http://codeforces.com/contest/1230/problem/C

time limit per test:

2 seconds

memory limit per test:

256 megabytes

input:

standard input

output:

standard output

题目大意：

两个骰子可以进行组合，第一个大于等于第二个骰子，每个骰子6种情况所以一共有21中图形。给一个无向图，向边上放置上述图形，要求可以有的边上没有骰子，并且边上的骰子一部分对着一个点，要求对着一个点的所有骰子的点数相同。输出可以放置图形的最大值。

思路：

暴力列举出所有的点的临近部分骰子的点数，然后进行判断，在每种情况下有多少个边上可以放置两个骰子组成的图形。然后输出最大值。

代码：

 #include <bits/stdc++.h>

 using namespace std;

 typedef pair<int,int > P;

 const int N=;

 int vis[N][N];

 int arr[N];

 int n,m,a,b,ans=,cnt=;

 P mp[N];

 void check(){

     int u,v;

     memset(vis,,sizeof(vis));

     cnt=;

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

         u=arr[mp[i].first];

         v=arr[mp[i].second];

         if(u>v){

             swap(u,v);

         }

         if(vis[u][v]==){

             vis[u][v]=;

             cnt++;

         }

     }

     ans=max(cnt,ans);

 }

 void dfs(int a){

     if(a==n+){

         check();

         return ;

     }

     for(int i=;i<=;i++){

         arr[a]=i;

         dfs(a+);

     }

 }

 int main(){

     memset(mp,,sizeof());

     memset(vis,,sizeof());

     cin>>n>>m;

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

         scanf("%d%d",&a,&b);

         mp[i]={a,b};

     }

     dfs();

     cout<<ans<<endl;

     return ;

 }

另一种思路：

当n<7时有多少个边就有多少个dominoes，因为每个点与点之间都可以相连，并且不会使用同一个dominoes。当等于7时，必定有一个是重复的。

解析：https://blog.csdn.net/qq_38946354/article/details/101271185

巴特西

C. Anadi and Domino

C. Anadi and Domino

最新文章

热门文章