首页 > 代码库 > CSU 1116 Kingdoms(枚举最小生成树)

CSU 1116 Kingdoms(枚举最小生成树)

题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1116

解题报告:一个国家有n个城市,有m条路可以修,修每条路要一定的金币,现在这个国家只有K个金币,每个城市有一些人,要你求怎么修路使得总的费用在K的范围内,同时使得跟首都连接的城市的人口(包括首都的人口)要最多,问最多的人口是多少。

枚举连接哪些城市,然后分别构造最小生成树。

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 20; 7 int pop[maxn],mat[maxn][maxn]; 8 int T,n,m,k; 9 10 int prim(int d,int& ans)11 {12     int visit[maxn],f = 1;13     memset(visit,0,sizeof(visit));14     d = (d << 1) + 1;15     for(int i = 1;i <= n;++i)16     {17         visit[i] = d & 1;18         d >>= 1;19     }20     int tot = 0;21     visit[1] = 2;   //等于2才是在集合中的 22     while(1)23     {24         int l = -1,temp = 0x7fffffff;25         for(int i = 1;i <= n;++i)26         if(visit[i] == 2)27         {28             for(int j = 1;j <= n;++j)29             if(visit[j] == 1 && mat[i][j] < temp)30             {31                 l = j;32                 temp = mat[i][j];33             }34         }35         if(l == -1 || temp > 100000) break;36         tot += temp;37         visit[l] = 2;38     }39     ans = 0;40     for(int i = 1;i <= n;++i)41     if(visit[i] == 2)42     ans += pop[i];43     return tot;44 }45 46 int main()47 {48     scanf("%d",&T);49     while(T--)50     {51         scanf("%d%d%d",&n,&m,&k);52         for(int i = 1;i <= n;++i)53         scanf("%d",&pop[i]);54         int x,y,z;55         memset(mat,0x3f,sizeof(mat));56         while(m--)57         {58             scanf("%d%d%d",&x,&y,&z);59             mat[x][y] = mat[y][x] = min(mat[x][y],z);60         }61         int tot = 0,t;62         for(int i = 0;i <= (1 << (n-1))-1;++i)63         {64             int temp = prim(i,t);65             if(temp <= k) tot = max(tot,t);66         }67         printf("%d\n",tot);68     }69     return 0;70 }
View Code

 

CSU 1116 Kingdoms(枚举最小生成树)