题目大意:n个点,m条边,每条边有颜色,生成一棵树,要求边的颜色数最少,输出最小值。

边多、点少,稠密图,但不能直接去重边,因为颜色是很重要的。因为颜色数量不超过12,那就用二进制存储颜色,输出的结果也是1到12之间!

用邻接矩阵存储边,暴力枚举每种颜色是否选,时间复杂度,接着搜索判断是否连通。因为只需要知道能不能到达,不需要找最短路,搜过不需要再搜,时间复杂度跟Flood Fill是一样的,因为用邻接矩阵,所以是O(n*n)。总时间复杂度是可以接受。

#include <bits/stdc++.h>
using namespace std;
int t, n, m, s, i, j, k, a, b, c, ans;
int v[105], mp[105][105];
int ok(int a){
    int i, b;
    v[a] = ++c;
    for(b=2; b<=n; b++){
        if(!v[b] && (mp[a][b]&m) && ok(b)) break;
    }
    return c == n;
}
void dfs(int k, int x, int y){
    int i;
    if(y >= ans) return;
    if(k > s){
        memset(v, c=0, sizeof(v));
        if((m=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(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;
}