BZOJ1016 [JSOI2008]最小生成树计数 【kruskal+状态压缩】

tonyfang posted @ 2016年8月12日 20:11 in BZOJ with tags OI c++ , 761 阅读

【题解】

大概就是先求出mct。

然后有个结论可以证明:就是在不同的mct中,每种权值的边用的是一样的。

然后我们就求出mct然后枚举就行啦

# include <stdio.h>
# include <algorithm>

using namespace std;

int n, m, fa[666666];
struct edge {
	int u, v, w;
}e[666666];
int ls[666666], lsn=0, MCT=0;
int used[666666];
inline int cmp(edge a, edge b) {
	return a.w < b.w;
}
inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}

inline bool chk(int pos, int x) {
	for (int i=1; i<=n; ++i) fa[i] = i;
	int cnt=0, mct = e[pos].w * used[e[pos].w];
	for (int i=pos; e[pos].w == e[i].w; ++i) {
		if(x&1) {
			int fu = getf(e[i].u), fv = getf(e[i].v);
			if(fu != fv) {
				fa[fu] = fv;
				++cnt;
			}
		}
		x >>= 1;
	}
	if(cnt == n-1) return mct == MCT;
	bool ok=0;
	for (int i=1; i<=m; ++i) {
		if(e[i].w == e[pos].w) continue;
		int fu = getf(e[i].u), fv = getf(e[i].v);
		if(fu == fv) continue;
		fa[fu] = fv;
		mct += e[i].w;
		++cnt;
		if(cnt == n-1) {
			ok=1;
			break;
		}
	}
	return ok && mct == MCT;
}

int main() {

	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; ++i) {
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
		ls[++lsn] = e[i].w;
	}
	sort(ls+1, ls+lsn+1);
	lsn=unique(ls+1, ls+lsn+1) - ls;
	for (int i=1; i<=m; ++i) 
		e[i].w = lower_bound(ls+1, ls+lsn+1, e[i].w) - ls;
	
	sort(e+1, e+m+1, cmp);
	
	for (int i=1; i<=n; ++i) fa[i] = i;
	
	int cnt=0;
	bool ok=0;
	
	for (int i=1; i<=m; ++i) {
		int fu = getf(e[i].u), fv = getf(e[i].v);
		if(fu == fv) continue;
		fa[fu] = fv;
		used[e[i].w] ++;
		MCT += e[i].w;
		++cnt;
		//printf("cnt=%d, MCT=%d\n", cnt, MCT);
		if(cnt == n-1) {
			ok=1;
			break;
		}
	}
	//printf("%d\n", MCT);
	//printf("USED=%d\n", used[2]);
	if(! ok) {
		puts("0");
		//puts("gg");
		return 0;
	}
	
	int ans = 1, j, now;
	
	for (int i=1; i<=m; i=j) {
		j=i+1;
		while(e[i].w == e[j].w) ++j;
		if(used[e[i].w]) {
			now = 0;
			int gs = j-i;
//			printf("To: %d\n", (1<<gs));
			for (int k=0; k<(1<<gs); ++k) {
				int gs2 = 0, kk = k;
				while(kk) {
					gs2 += kk&1;
					kk >>= 1;
				}
//				printf("k=%d, gs=%d\n", k, gs2);
				if(gs2 != used[e[i].w]) continue;
				if(chk(i, k)) ++now;
			}
			ans = ans * now % 31011;
		}
	}	
	
	
	printf("%d\n", ans);
	return 0;
}
BSNL Customer Care N 说:
2023年2月06日 16:39

BSNL customer care number of each state regarding to BSNL services towards toll free and paid numbers which are accessed from own and other networks across the country. BSNL Customer Care No The new digital era based support system contributing a lion’s sharing related to all telecom services, also find the new email address providing BSNL complaint process for payment failed issues for any digital payment service failure related issues like repayment.

www.modelpaper2020.i 说:
2023年4月20日 01:02

Board Model Paper 2023 Aspirants who had Registered for the Board 12th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. www.modelpaper2020.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter