H - Kingdoms UVA - 12507——最小生成树＋dfs

男娘i 2022-06-13 02:16 114阅读 0赞

Think:  
1思路:  
1>将1号结点预处理，通过图的连通性满足其余结点与1号结点直接或间接连接  
2>dfs枚举情况不断试探最优解

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int T, n, m, K, w[24], f[24], book[24];
    int ans, cnt;
    
    struct node {
        int u, v, c;
    }edge[104];
    bool cmp(node a, node b){
        return a.c < b.c;
    }
    int getf(int v){
        if(f[v] == v)
            return f[v];
        else {
            f[v] = getf(f[v]);
            return f[v];
        }
    }
    bool Merge(int u, int v){
        int t1 = getf(u);
        int t2 = getf(v);
        if(t1 == t2)
            return false;
        else {
            f[t1] = t2;
            return true;
        }
    }
    bool Tmp(){
        for(int i = 1; i <= n; i++)
            f[i] = i;
        int k = 0, j = 0;
        for(int i = 0; i < m; i++){
            int u = edge[i].u;
            int v = edge[i].v;
            int c = edge[i].c;
            if(book[u] && book[v] && Merge(u, v)){
                j++;
                k += c;
            }
            if(j >= cnt-1)/*连通图*/
                break;
        }
        if(j >= cnt-1 && k <= K)
            return true;
        else
            return false;
    }
    void dfs(int step){
       /*枚举尝试试探最优解*/
        if(step > n){
            if(Tmp()) {
                int sum = 0;
                for(int i = 1; i <= n; i++){
                    if(book[i])
                        sum += w[i];
                }
                ans = max(ans, sum);
            }
            return;
        }
    
        cnt++;
        book[step] = 1;
        dfs(step+1);
    
        cnt--;
        book[step] = 0;
        dfs(step+1);
    
    }
    
    int main(){
        scanf("%d", &T);
        while(T--){
            scanf("%d %d %d", &n, &m, &K);
            for(int i = 1; i <= n; i++)
                scanf("%d", &w[i]);
            for(int i = 0; i < m; i++)
                scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].c);
            sort(edge, edge+m, cmp);
    
            ans = 0;
            memset(book, 0, sizeof(book));
    
            book[1] = 1;
            cnt = 1;
            dfs(2);
    
            printf("%d\n", ans);
        }
        return 0;
    }

[vjudge]: https://vjudge.net/problem/UVA-12507