Clarke and MST HDU - 5627

本文主要是介绍Clarke and MST HDU - 5627，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=5627

要求一棵且运算结果最大的SPT 肯定不能简单按权值排序

贪心考虑 枚举二进制位 如果2^i可以被满足 完全可以牺牲掉2^(i-1) 2^(i-2)...

枚举到2^i时 从目前所有边中找出边权的二进制位中i位为1的边 看能否将图连通 能的话就把低位的范围限定在所有边权的二进制位中i位为1的边中 若不连通则放弃2^i 转而在当前所有边中凑2^(i-1)

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=3e5+10;struct node
{int u,v,w;
};node edge[maxn];
int f[maxn],book[maxn];
int pre[50];
int n,m;void init()
{int i;pre[0]=1;for(i=1;i<=29;i++){pre[i]=2*pre[i-1];}
}int getf(int p)
{if(f[p]==p) return p;else return f[p]=getf(f[p]);
}void unite(int u,int v)
{int fu,fv;fu=getf(u),fv=getf(v);if(fu!=fv){f[fv]=fu;}
}int main()
{int t,i,j,ans,cnt;init();scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i=1;i<=m;i++){scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);}memset(book,0,sizeof(book));ans=0;for(j=29;j>=0;j--){for(i=1;i<=n;i++) f[i]=i;for(i=1;i<=m;i++){if(!book[i]&&(edge[i].w&(1<<j))){unite(edge[i].u,edge[i].v);}}cnt=0;for(i=1;i<=n;i++){if(f[i]==i) cnt++;}if(cnt==1){for(i=1;i<=m;i++){if(!book[i]&&(edge[i].w&(1<<j))){book[i]=1;}}ans+=(1<<j);}}printf("%d\n",ans);}return 0;
}

 

这篇关于Clarke and MST HDU - 5627的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---