三原色图 1006

近期某道题的代码

苦逼的我写了一下午，才发现两个最小生成树在边数大于n-1后有可能最小的选择会改变。

比如将所有边排列好了为

1 2 3 4 5 8

第一个最小生成树一开始是128 比 第二个最小生成树 345 小

但当用4条边时，就成了1238=14 ，第二个为 1345为13 变化了。。。。

改了之后又出现了最大值越界，也是没谁了。。。。

吸粉大法好！！！！！！！！

#include
using namespace std;
const int maxn=105;
const int INF=0x3f3f3f3f;
int T;
int n,m;
int F[maxn];
bool vis[2][maxn];
int Find(int x)
{
    return F[x]==x?x:F[x]=Find(F[x]);
}
void join(int a,int b)
{
    int fa=Find(a);
    int fb=Find(b);
    if(fa!=fb)
    {
        F[fb]=fa;
    }
}
class Edge
{
    public:
        int s,e,len;
        char c;
};
bool operator < (const Edge a,const Edge b)
{
    return a.len<b.len;
}
Edge edge[maxn];
bool check(int i)
{
    return (Find(edge[i].s)!=Find(edge[i].e));
}
int solve(char c)
{
    int sum=0;
    int p;
    if(c=='R')p=0;
    else p=1;
    for(int i=1;i<=n;i++)
    {
        F[i]=i;
    }
    int cnt=0;
    for(int i=0;i!=m;i++)
    {
        if(check(i)&&(edge[i].c=='G'||edge[i].c==c))
        {
            cnt++;
            sum+=edge[i].len;
            join(edge[i].s,edge[i].e);
            vis[p][i]=1;
        }
        if(cnt==n-1)break;
    }
    if(cnt==n-1)return sum;
    else return INF;
}
int main()
{
    scanf("%d",&T);
    for(int t=1;t<=T;t++)
    {
        scanf("%d %d",&n,&m);
        for(int i=0;i!=m;i++)
        {
            scanf("%d %d %d %c",&edge[i].s,&edge[i].e,&edge[i].len,&edge[i].c);
        }
        sort(edge,edge+m);
        memset(vis,0,sizeof(vis));
        int ans[2];
        ans[0]=solve('R');ans[1]=solve('B');
        cout<<"Case #"<<t<<":"<<endl;
        for(int i=1;i<=m;i++)
        {
            if((ans[0]==INF&&ans[1]==INF)||i<n-1)cout<<"-1"<<endl;
            else
            {
                cout<<min(ans[0],ans[1])<<endl;
                for(int p=0;p!=2;p++)
                {
                    for(int q=0;q!=m;q++)
                    {
                        if(!vis[p][q])
                        {
                            ans[p]+=edge[q].len;
                            vis[p][q]=1;
                            break;
                        }
                    }
                }
            }
        }
    }
    return 0;
}