题目背景

2018百度之星入围赛T6

题目描述

\(Jay\) 有一张 \(n\) 个点 \(m\) 条边的无向图， 所有点按照 \(1,2,⋯,n\) 标号， 每条边有一
个正整数权值以及一种色光三原色红、 绿、 蓝之一的颜色。
现在 \(Jay\) 想选出恰好 \(k\) 条边，满足只用这 \(k\) 条边之中的红色边和绿色边就能使 \(n\)
个点之间两两连通， 或者只用这 \(k\) 条边之中的蓝色边和绿色边就能使 \(n\) 个点之
间两两连通， 这里两个点连通是指从一个点出发沿着边可以走到另一个点。
对于每个 \(k \in [1,m],k \in Z\) ， 你都需要帮 \(Jay\) 计算选出恰好 \(k\) 条满足条件的边的权值之和的最小值。

\(1 \le n, m \le 100\)

$1 \le $ 边权 \(w \le 1000\)

题解

一道最小生成树练手好题 ，不需要什么复杂的技巧，理解了原理就可以。

以蓝绿，红绿为所选颜色跑两遍最小生成树。一旦能够生成树，剩下的边就从小到大排序，依次选完。

注意事项

一定要判断能不能生成最小生成树！！！

排序只需要排一次。

分清楚哪里\(break\) ，哪里\(continue\) 。

\(n==1\)时好像要输出一个\(0\)

Code

#include<bits/stdc++.h>
#define N (220)
using namespace std;
struct xbk{int st,ed,v;char f;}e[N];
char opt;
int T,n,m,sum,cnt,flag,now[N],fa[N],ans1[N],ans2[N];
bool flag1,flag2,used[N];
inline int read(){
	int w=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9'){
		w=(w<<3)+(w<<1)+(ch^48);
		ch=getchar();
	}
	return w;
}
inline bool cmp(xbk a,xbk b){return a.v<b.v;}
inline int mfind(int x){
	if(fa[x]!=x) return fa[x]=mfind(fa[x]);
	return fa[x];
}
inline void init(){
	cnt=0;
	memset(now,0,sizeof(now));
	memset(used,0,sizeof(used));
	for(int i=1;i<=m;i++) fa[i]=i;
}
inline void Solo(){
	init();
	for(int i=1;i<=m;i++){
		int nx=mfind(e[i].st),ny=mfind(e[i].ed);
		if(nx==ny||e[i].f=='R') continue;
		fa[nx]=ny;
		used[i]=1;
		cnt++;
		ans1[cnt]=ans1[cnt-1]+e[i].v;
		if(cnt==n-1){
			flag1=1;
			int tot=0;
			for(int j=1;j<=m;j++) if(!used[j]) now[++tot]=e[j].v;
			sort(now+1,now+1+tot);
			for(int j=1;j<=tot;j++) ans1[j+cnt]=ans1[j+cnt-1]+now[j];
			break;
		}
	}
	init();
	for(int i=1;i<=m;i++){
		int nx=mfind(e[i].st),ny=mfind(e[i].ed);
		if(nx==ny||e[i].f=='B') continue;
		fa[nx]=ny;
		used[i]=1;
		cnt++;
		ans2[cnt]=ans2[cnt-1]+e[i].v;
		if(cnt==n-1){
			flag2=1;
			int tot=0;
			for(int j=1;j<=m;j++) if(!used[j]) now[++tot]=e[j].v;
			sort(now+1,now+1+tot);
			for(int j=1;j<=tot;j++) ans2[j+cnt]=ans2[j+cnt-1]+now[j];
			break;
		}
	}
	return;
}
int main(){
	T=read();
	while(T--){
		printf("Case #%d",++flag);
		puts(":");
		n=read(),m=read();
		for(int i=1;i<=m;i++){
			e[i].st=read(),e[i].ed=read(),e[i].v=read();
			cin>>opt;
			e[i].f=opt;
		}
		sort(e+1,e+1+m,cmp);
		if(n==1){
			int nw=0;
			puts("0");
			for(int i=1;i<=m;i++){
				nw+=e[i].v;
				printf("%d\n",nw);
			}
			continue;
		}
		flag1=0,flag2=0;
		Solo();
		if(!flag1&&!flag2){
			for(int i=1;i<=m;i++) puts("-1");
			continue;
		}
		for(int i=1;i<=m;i++){
			if(i<n-1){puts("-1");continue;}
			if(flag1&&!flag2) printf("%d\n",ans1[i]);
			if(flag2&&!flag1) printf("%d\n",ans2[i]);
			if(flag1&&flag2) printf("%d\n",min(ans1[i],ans2[i]));
		}
	}
	return 0;
}

完结撒花❀