2018"百度之星"程序设计大赛 - 资格赛 P1006三原色图(MST,并查集)

举报
小哈里 发表于 2022/05/10 22:37:55 2022/05/10
【摘要】 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200