最小生成树

输入共有 2 行。
第一行包含一个正整数 M，代表给定图中每个点的特征值都是小于 M 的非负整数。
第二行是一个长度为M 的字串S，此字串由数字字元组成(也就是'0' 至'9')，第i 个数字字元即代表特征值为 i-1 的点的个数。

C++11(clang++ 3.9) 解法, 执行用时: 2279ms, 内存消耗: 2296K, 提交时间: 2018-04-18 18:50:03

#include<cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=(int)2e6;
int fa[N],num[N],m,ma[N];
char s[N];
ll ans;
int find(int x)
{
	return x==fa[x]? x:fa[x] = find(fa[x]);
}
void link(int x,int y)
{
	int a,b;
	a = find(x),b = find(y);
	if(a!=b){
		ans += ll(x&y)*(num[x]+num[y]-1);
		num[x] = num[y] = 1;
		fa[b] = a;
	}
}


int main (){
	scanf ("%d%s",&m,s);
	for (int i=0;i<m;i++){
		fa[i]=i;
		num[i]=s[i]-'0';
	}
	int inf=m-1;
	for(int i=0;i<m;i++){ 
		int x = i^inf;
		for(int j=x;;j=(j-1)&x){ 
			int y= j^i;
			if(num[y]){
				int z = y^inf;
				if(!ma[z^i]){
					for(int k=z;;k=(k-1)&z){
						int c= k^i;
						if(num[c])
							link(y,c);
						ma[c] = 1;
						if(!k) break;
					}
				} 
			}
			if(!j) break;
		} 
	}
	printf ("%lld\n",ans);
	
	return 0;
}

详情