当前位置 : 主页 > 网页制作 > css >

Anadi and Domino--codeforces div2

来源:互联网 收集:自由互联 发布时间:2021-06-13
题目链接:https://codeforces.com/contest/1230/problem/C 题目大意:21枚多米诺牌,给你一个图,将多米诺牌放到图的边上,由同一个点发出的所有边,边上多米诺牌对应该点的一侧相同。 such

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

题目大意:21枚多米诺牌,给你一个图,将多米诺牌放到图的边上,由同一个点发出的所有边,边上多米诺牌对应该点的一侧相同。

such as:

 

题解:暴力枚举,即先给每个点一个值,然后判断在这种情况下可以放置多少个多米诺牌,枚举的时候可以dfs递归

#include<bits/stdc++.h>
using namespace std;
const int N=200;
int n,m;
int d[N];
int l[N],r[N];
int ans=0;
bool mark[N][N];
void check(){
    int sum=0;
    memset(mark,0,sizeof(mark));
    for(int i=1;i<=m;i++){
        int a=d[l[i]];
        int b=d[r[i]]; 
        if(a>b) swap(a,b);
        
        if(!mark[a][b]){//判断a,b这种牌有没有被用过; 
            mark[a][b]=1;
            sum++;
        }
    }
    ans=max(ans,sum);
}
void dfs(int x){
    if(x==n+1){//如果所有的点都被赋值,那就判断在这种情况下可以多少放置多少个; 
        check();
        return ;
    }
    for(int i=1;i<=6;i++){
        d[x]=i;
        dfs(x+1);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l[i],&r[i]); //指的是从l到r有一条边 
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}
网友评论