2019ICPC南昌站E.Bob's Problem
一个图，边分为黑边和白边，白边最多能选择k条，并且要保持图连通的情况下，求一个权值和最大的子图
首先贪心的想的话，肯定是要把黑边全选上（因为边权无负值），选完所有黑边之后并查集缩点（一直不知道这个操作叫缩点天啊，我是憨憨），然后缩完的图，用白边跑一次最大生成树，
如果k还有剩余，再把刚才没选的白边也加上。一点点就是多样例输入记得清空，莫名其妙（智商掉线）W了几发。。。
struct IN
{
ll u,v,w;
IN (ll uu,ll vv,ll ww):u(uu),v(vv),w(ww){}
bool operator < (IN b)
{
return w>b.w;
}
};
ll fa[MAXN];
ll find(ll x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
fast;
int t;cin>>t;
while(t--)
{
ll n,m,k;
cin>>n>>m>>k;
vector<IN>ed0,ed1,ed2;
rep(i,m)
{
int x,y,w,c;cin>>x>>y>>w>>c;
if(c==0) ed0.push_back(IN(x,y,w));
else ed1.push_back(IN(x,y,w));
}
rpp(i,n) fa[i]=i;
ll ans=0;
ll cnt=n;
rep(i,ed0.size())
{
ll f1=find(ed0[i].u),f2=find(ed0[i].v);
if(f1!=f2) fa[f2]=f1,--cnt;//连通块个数减一
ans+=ed0[i].w;
}
sort(all(ed1));
rep(i,ed1.size())
{
if(k==0) break;
ll f1=find(ed1[i].u),f2=find(ed1[i].v);
if(f1!=f2) fa[f2]=f1,--cnt,--k,ans+=ed1[i].w;
else ed2.push_back(ed1[i]);
}
sort(all(ed2));
rep(i,ed2.size())
{
if(k==0) break;
ans+=ed2[i].w;
--k;
}
if(cnt>1) cout<<"-1"<<endl;
else cout<<ans<<endl;
}
return 0;
} 
投递多益网络等公司10个岗位