本文共 1353 字，大约阅读时间需要 4 分钟。

这道题在大一团队训练赛上见过，很多人一次过了，是一道dfs+最小生成树，王昊天学长讲的时候也是三言两语带过，我有点不确定哈理工的水平什么·时候这么高了。。

组合dfs取出m个点，用这m个点构建最小生成树，这m个点的权值和是一定的，故边权值最小，则比才会最小；

思路：在Edge中选最小的，若这两点有一个不是m个点中的，就不把它放入树中；以为自己过不了，结果一次ac；

这道题有很多人卡在权值比上，精度没把握好的就会wr,其实用乘法更好，解决了精度问题；

幸好我提前看了discuss,发现了坑和解决办法；

代码：

#include
   
    #include
    
     #include
     
      using namespace std;int n,m;const int maxn=400;int edge_wei[maxn][maxn];int node_wei[maxn];int fa[maxn];int visit[maxn];int k[maxn];int nw;int ew;int start;int shu;struct Edge{    int u;    int v;    int weight;};Edge a[maxn];void init(){    int i;    for(i=1;i<=n;i++)        fa[i]=i;}int find(int u){    return fa[u]==u?fa[u]:fa[u]=find(fa[u]);}void join(int u,int v){    fa[find(u)]=find(v);}bool cmp(Edge x,Edge y){    return x.weight
      
       >n>>m)    {        if(n==0&&m==0)            break;        int i,j;        memset(visit,0,sizeof(visit));         start=0;        for(i=1;i<=n;i++)        {            cin>>node_wei[i];        }        for(i=1;i<=n;i++)        {            for(j=1;j<=n;j++)            {                cin>>edge_wei[i][j];                if(j>=i)                    continue;                  a[start].u=i;                  a[start].v=j;                  a[start++].weight=edge_wei[i][j];            }        }        sort(a,a+start,cmp);         nw=1;         ew=1500;        select(1,1);        for(i=0;i
      
     
    
   

转载地址：http://jygji.baihongyu.com/