首页 > ACM题库 > HDU-杭电 > HDU 4133-StrangeStandard-最小生成树-[解题报告]HOJ
2015
04-16

HDU 4133-StrangeStandard-最小生成树-[解题报告]HOJ

StrangeStandard

问题描述 :

Nowadays, WHUACMer use a strange standard to evaluate a natural number.The evaluating value of a natural number is the amount of it’s divisors.If a number m has bigger evaluating value than all the numbers smaller than it, we call it a good number. Now give you a number n, find the maximum good number which is not bigger than n.

输入:

The first line contains a single integer T(T<=10), indicating the number of test cases.
For each test case,there is only one line which only contains one number n(1 <= n <= 2 000 000 000)

输出:

The first line contains a single integer T(T<=10), indicating the number of test cases.
For each test case,there is only one line which only contains one number n(1 <= n <= 2 000 000 000)

样例输入:

1
1000

样例输出:

Case #1: 840

/*
题目大意:求最大生成树。

     题目分析:转换一下思维,将最小改为最大就可以了,题目数据有重边,使用kruskal算法无影响,
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=120002;
int n,m,k,flag,father[maxn],vis[maxn],col[maxn];
long long ans,sum;
struct node
{
    int u,v,cost;
} p[maxn];
int cmp(node a,node b)
{
    return a.cost>=b.cost;
}
int find(int i)
{

    return father[i]==i?i:find(father[i]);
}
set<int>s[maxn];
int main()
{
    int i,j,u,v,t;
    cin>>t;
    while(t--)
    {
        scanf("%d%d",&n,&m);
        ans=sum=0;
        for(i=0; i<=n; i++)father[i]=i;
        memset(vis,0,sizeof(vis));
        memset(col,0,sizeof(col));
        for(i=1; i<=n-1; i++)
        {
            scanf("%d%d%d",&p[i].u,&p[i].v,&p[i].cost);
        }
        while(m--)
        {
            cin>>k;
            vis[k]=1;
        }
        sort(p+1,p+n,cmp);
        for(i=1; i<=n-1; i++)
        {
            int x=find(p[i].u);
            int y=find(p[i].v);

            // cout<<"idx "<<i<<" fx "<<fx<<" fy "<<fy<<" u "<<p[i].u<<" v "<<p[i].v<<" cost "<<p[i].cost<<endl;
            if(vis[x]&&vis[y])
            {
                sum+=p[i].cost;
            }else father[y]=x,vis[x]=(vis[x]||vis[y]);

        }
        cout<<sum<<endl;
    }
    return 0;
}
/*
2
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0
5 3
2 1 5
1 0 8
2 4 5
1 3 4
2
4
0
*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/azheng51714/article/details/9002337


  1. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。