牛客OI周赛11-普及组 C Colorful

摘录 https://blog.nowcoder.net/n/c3ed459a06074283be1cf9ea1e2c9261

#include<bits/stdc++.h>
using namespace std;

int t,n,m,a,b,c,ans,k,s;

int v[105],mp[105][105];   

int ok( int x )
{
    v[x]=++c;
    for( int i=2;i<=n;i++ )
    {
        if( !v[i] && ( mp[x][i] & m ) && ok(i) ) break;  // 搜索剪枝 
    } 
    return c==n;
}

void dfs( int k,int x,int y )   // k是枚举到第几个颜色  // x 枚举颜色方案 //   y是颜色个数 
{
    if( y>=ans ) return; // 剪枝 
    if( k>s )  //枚举完成 
    {
        memset( v,0,sizeof(v) ); // 判断是否联通前的 初始化 
        c=0;m=x;                 // c 计数联通块大小  m 为颜色方案 
        if( x && ok(1) ) ans=y;  // 更新答案 
    }
    else
    {
        dfs(k+1,x,y);
        dfs(k+1,x|( 1<<k ),y+1);
    }
}


int main()
{
    scanf("%d",&t);
    while( t-- )
    {
        scanf("%d%d%d",&n,&m,&s);
        ans=s;
        memset(mp,0,sizeof(mp));
        for( int i=1;i<=m;i++ )   //    邻接矩阵存边 
        {
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b]=mp[b][a]=mp[a][b] | (1<<c);
        }
        dfs(1,0,0);
        printf("%d\n",ans); 
    }
    return 0;
}