Connect the Cities&&http://acm.hdu.edu.cn/showproblem.php?pid=3371

최소 생성 트리 변형 문제는 해석하지 않습니다. 여기는 입력량이 비교적 많기 때문에 입력 외장을 사용하는 것이 좋습니다...
AC 코드:

#include<iostream>
#include<string.h>
#include<cstdio>
#include<string>
#include<limits.h>
#include<algorithm>
#include<queue>
#define N 80000
#define M 505
using namespace std;
typedef struct
{
    int x;
    int y;
    int len;
}Node;
Node s[N];
int res,Father[M];
int n,m,k;
bool cmp(Node a,Node b)
{return a.len<b.len;}
void in(int &a)
{
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    for(a=0;ch>='0'&&ch<='9';ch=getchar()) a=a*10+ch-'0';

}
void init()
{
    res=0;
    for(int i=1;i<=n;++i) Father[i]=i;
}
int Find(int x)
{
    if(x==Father[x]) return x;
    return Father[x]=Find(Father[x]);
}
int main()
{
    int T;
    in(T);
    while(T--)
    {
        //scanf("%d%d%d",&n,&m,&k);
        in(n),in(m),in(k);
        init();
        for(int i=0;i!=m;++i)
        {
            int a,b,c;
            //scanf("%d%d%d",&a,&b,&c);
            in(a),in(b),in(c);
            s[res].x=a,s[res].y=b,s[res++].len=c;
        }
        int sum=0,ans=0;
        bool flag=false;
        for(int i=0;i!=k;++i)
        {
            int t,a;
            //scanf("%d%d",&t,&a);
              in(t),in(a);
            for(int i=0;i!=t-1;++i)
            {
                int b;
                //scanf("%d",&b);
                in(b);
                if(!flag)
                {
                    int x=Find(a);
                    int y=Find(b);
                    if(x!=y) {Father[y]=x;sum++;}
                }
              if(sum==n-1) flag=true;
            }
        }
        if(flag) printf("0
");
        else
        {
            sort(s,s+res,cmp);
            for(int i=0;i!=res;++i)
            {
                if(sum==n-1) break;
                int x=Find(s[i].x);
                int y=Find(s[i].y);
                if(x!=y) {Father[x]=y;sum++;ans+=s[i].len;}
            }
            if(sum==n-1) printf("%d
",ans);
            else  printf("-1
");
        }
    }return 0;
}