描述

传送门：2018”百度之星”程序设计大赛 - 资格赛1006

度度熊有一张 $n$ 个点 $m$ 条边的无向图，所有点按照 $1,2,⋯,n$ 标号，每条边有一个正整数权值以及一种色光三原色红、绿、蓝之一的颜色。

现在度度熊想选出恰好 $k$ 条边，满足只用这 $k$ 条边之中的红色边和绿色边就能使 n 个点之间两两连通，或者只用这 $k$ 条边之中的蓝色边和绿色边就能使 $n$ 个点之间两两连通，这里两个点连通是指从一个点出发沿着边可以走到另一个点。

对于每个 $k=1,2,⋯,m$，你都需要帮度度熊计算选出恰好 $k$ 条满足条件的边的权值之和的最小值。

Input

第一行包含一个正整数 T，表示有 T 组测试数据。

接下来依次描述 T 组测试数据。对于每组测试数据：

第一行包含两个整数 n 和 m，表示图的点数和边数。

接下来 m 行，每行包含三个整数 a,b,w 和一个字符 c，表示有一条连接点 a 与点 b 的权值为 w、颜色为 c 的无向边。

保证$ 1 \leq T \leq 100$，$1 \leq n,m \leq 100$，$1 \leq a,b \leq n$，$1 \leq w \leq 1000$，$c \in \{R,G,B\}$，这里 R,G,B 分别表示红色、绿色和蓝色。

Output

对于每组测试数据，先输出一行信息 “Case #x:”（不含引号），其中 $x$ 表示这是第 $x$ 组测试数据，接下来 $m$ 行，每行包含一个整数，第 $i$ 行的整数表示选出恰好 $i$ 条满足条件的边的权值之和的最小值，如果不存在合法方案，输出 −1，行末不要有多余空格。

Examples

intput

output
1
2
3
4
5
6
7
8
9
Case #1:
-1
-1
-1
9
10
12
17
22

思路

显然是求最小生树，但是加了颜色限制。

按两种限制建两个最小生成树，在n-1条边的时候取min。大于n-1条边的时候就从没选的边里选一条最短的。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define repd(i,a,n) for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e2+5;

int Fa[N],test=999,Dis[N];
struct node {
    int a,b,s,Used;
    char col;
    bool operator< (node e) const {
        return s<e.s;
    }
} Edge1[N],Edge2[N];

int Find(int x) {return Fa[x]==x? x:Fa[x]=Find(Fa[x]);}
bool Union(int x,int y) {int fa=Find(x),fb=Find(y);Fa[fa]=fb;return fa!=fb;}

int main() {
    int T,n,m;
    cin>>T;
    rep(Case,1,T+1) {
        cin>>n>>m;
        rep(i,0,n+1) Fa[i]=i;
        int x,y,w;
        char c;
        rep(i,0,m) {
            cin>>x>>y>>w>>c;
            Edge1[i]=Edge2[i]=(node) {x,y,w,0,c};
        }

        sort(Edge1,Edge1+m);
        sort(Edge2,Edge2+m);

        int Clock1=0,Clock2=0,tem1=0,tem2=0;    //不要蓝色建最小生成树
        for(int i=0; i<m&&Clock1<n-1; i++)
            if(Edge1[i].col!='B'&&Union(Edge1[i].a,Edge1[i].b)) {
                tem1+=Edge1[i].s;
                Edge1[i].Used=1;
                Clock1++;
            }

        rep(i,0,n+1) Fa[i]=i;               //初始化并查集
        for(int i=0; i<m&&Clock2<n-1; i++)  //不要红色建最小生成树
            if(Edge2[i].col!='R'&&Union(Edge2[i].a,Edge2[i].b)) {
                tem2+=Edge2[i].s;
                Edge2[i].Used=1;
                Clock2++;
            }

        CRL(Dis,-1);
        if(Clock1==n-1||Clock2==n-1) {//如果找到了最小生成树

            if(Clock1!=n-1)         //如果没有蓝色无解，就给他附一个极大值
                tem1=0x3f3f3f;
            else if(Clock2!=n-1)    //如果没有红色无解
                tem2=0x3f3f3f;
            Dis[n-1]=min(tem1,tem2);

            int xa=-1,xb=-1;
            rep(i,n,m+1) {          //每次找没用过的最短边
                while(Edge1[++xa].Used);//两种情况分别找
                tem1+=Edge2[xa].s;
                Edge1[xa].Used=1;

                while(Edge2[++xb].Used);
                tem2+=Edge2[xb].s;
                Edge2[xb].Used=1;

                Dis[i]=min(tem1,tem2);
            }
        }
        
        printf("Case #%d:\n",Case);
        rep(i,1,m+1) printf("%d\n",Dis[i]);
    }
    return 0;
}