C++14(g++5.4) 解法, 执行用时: 95ms, 内存消耗: 1984K, 提交时间: 2019-12-27 10:12:44

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5e4+3;
int V, E, need;

struct Edge {
  int s, t, c, col;
};
vector<Edge> edges;

int p[MAXN];
int find(int x) {
  return p[x] = p[x] == x? x: find(p[x]);
}
pair<int, long long> gao(int acc) {
  for (auto &e: edges) if (e.col == 0) e.c += acc;
  long long tot = 0;
  int cnt = 0;
  for (int i = 0; i < V; i++) p[i] = i;

  sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) {
    if (a.c == b.c) return a.col < b.col;
    return a.c < b.c;
  });

  for (auto &e: edges) {
    int x = e.s, y = e.t;
    int px = find(x), py = find(y);
    if (px == py) continue;
    p[px] = py;
    tot += e.c;
    if (e.col == 0) cnt++;
  }
  for (auto &e: edges) if (e.col == 0) e.c -= acc;
  return {cnt, tot};
}

int main() {
  ios_base::sync_with_stdio(false);
  cin >> V >> E >> need;
  edges.resize(E); for (auto &e: edges) cin >> e.s >> e.t >> e.c >> e.col;

  int lo = -128, hi = 128;
  while (lo < hi) {
    int mid = (lo + hi + 256) / 2 - 128;
    auto tmp  = gao(mid);
    if (tmp.first >= need) lo = mid + 1;
    else hi = mid;
  }
  cout << gao(hi-1).second - need * (hi - 1) << endl;
}

C++ 解法, 执行用时: 113ms, 内存消耗: 3452K, 提交时间: 2022-06-19 11:12:01

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	long long x,y,d,c;
}E[100010];
long long n,m,need;
long long ans,fa[100010];
long long tot,white,anss;
int find(int x)
{
	if(x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
int cmp(edge a,edge b)
{
	if(a.d==b.d)return a.c<b.c;
	return a.d<b.d;
}
int kk(int x)
{
	for(int i=0;i<=n;i++)
	fa[i]=i;
	for(int i=1;i<=m;i++)
	if(!E[i].c)
	E[i].d+=x;
	sort(E+1,E+m+1,cmp);
	ans=0,tot=0,white=0;
	for(int i=1;i<=m;i++)
	{
		int f1=find(E[i].x),f2=find(E[i].y);
		if(f1==f2)
		continue;
		fa[f1]=f2;
		tot++;
		ans+=E[i].d;
		white+=(!E[i].c);
		if(tot==n-1)break;
	}
	for(int i=1;i<=m;i++)
	if(!E[i].c)E[i].d-=x;
	if(white>=need)
	return 1;
	return 0;
}
int main()
{
	cin>>n>>m>>need;
	for(int i=1;i<=m;i++)
	cin>>E[i].x>>E[i].y>>E[i].d>>E[i].c;
	int l=-101,r=101;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(kk(mid))
		{
			l=mid+1;
			anss=ans-need*mid;
		}
		else r=mid-1;
	}
	cout<<anss<<endl;
}