2018"百度之星"程序设计大赛 - 资格赛 P1006三原色图(MST,并查集)
【摘要】
problem
给一张n个点m条边的有向图,每条边有一个正整数权值以及一种色光三原色红、绿、蓝之一的颜色。恰好选出k条边,满足只用这k条边之中的红色边和绿色边(或者蓝色边和绿色边)就能使n个点之间两两连...
problem
- 给一张n个点m条边的有向图,每条边有一个正整数权值以及一种色光三原色红、绿、蓝之一的颜色。
- 恰好选出k条边,满足只用这k条边之中的红色边和绿色边(或者蓝色边和绿色边)就能使n个点之间两两连通
- 对于k==1…m,计算选出恰好k条满足条件的边的权值之和的最小值。
solution
- 当 k < n-1 时,分别求两种情况的最小生成树(红绿,蓝绿),记录每种情况用了哪些边。
- 当 k > n-1 时,按照边权从小到大找没有用过的直接加
codes
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1100, inf=2147000000;
//Grape
int n, m;
struct Edge{ int u, v, w; char c; }e[maxn];
bool cmp(Edge a, Edge b){return a.w<b.w;}
//UnionFindSet
int fa[maxn];
void init(int _n){for(int i = 1; i <= _n; i++)fa[i]=i;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x),y=find(y);fa[x]=y;}
//MST
int vis[3][maxn];//记录边
int solve(int s){
memset(vis[s],0,sizeof(vis[s]));
int mst = 0;
init(n);
for(int i = 1; i <= m; i++){
if(s==1&&e[i].c=='B')continue;
if(s==2&&e[i].c=='R')continue;
int x = find(e[i].u), y = find(e[i].v);
if(x != y){
merge(x,y);
mst += e[i].w;
vis[s][i] = 1;
}
}
for(int i = 2; i <= n; i++)//判断是否联通
if(find(i)!=find(1))return -1;
return mst;
}
//Timu
int ans1[maxn], ans2[maxn];
int main(){
int w; scanf("%d",&w);
for(int _w = 1; _w <= w; _w++){
printf("Case #%d:\n", _w);
memset(ans1,-1,sizeof(ans1));
memset(ans2,-1,sizeof(ans2));
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++)
scanf("%d%d%d %c",&e[i].u,&e[i].v,&e[i].w,&e[i].c);
sort(e+1,e+m+1,cmp);
for(int i = 1; i < n-1; i++)
printf("-1\n");
int mst1 = solve(1);
int mst2 = solve(2);
if(mst1==-1&&mst2==-1){//森林,无法联通
for(int i = n; i <= m; i++)
printf("-1\n");
continue;
}
int cur = n-1;
if(mst1==-1){//赋初始值
ans1[cur] = inf;
ans2[cur] = mst2;
}else if(mst2==-1){
ans1[cur] = mst1;
ans2[cur] = inf;
}else{
ans1[cur] = mst1;
ans2[cur] = mst2;
}
if(mst1!=-1){
for(int i = 1; i <= m; i++)
if(!vis[1][i]){cur++;ans1[cur]=ans1[cur-1]+e[i].w;}
}else for(int i = n; i <= m; i++)ans1[i] = inf;
cur = n-1;
if(mst2!=-1){
for(int i = 1; i <= m; i++)
if(!vis[2][i]){cur++;ans2[cur]=ans2[cur-1]+e[i].w;}
}else for(int i = n; i <= m; i++)ans2[i] = inf;
for(int i = n-1; i <= m; i++)
printf("%d\n",min(ans1[i],ans2[i]));
}
return 0;
}
文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。
原文链接:gwj1314.blog.csdn.net/article/details/81433098
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)