题目链接：点击打开链接
题目大意：略。
解题思路：Kruskal 算法 + 首先要将已经修建的道路进行并查集合并操作，用 set 存集合中结点的个数来判断是否所有点都已经操作完成，剩余的点按照基本操作进行就好了。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const int maxn=110; struct edge { int u,v,w,f; }es[maxn*maxn]; int n,m; int pre[maxn]; set<int> st; // 判断是否所有点都已经操作完成 void init() { st.clear(); m=n*(n-1)/2; for(int i=1;i<=n;i++) pre[i]=i; } int cmp(edge e1,edge e2) { if(e1.f==e2.f) return e1.w<e2.w; return e1.f>e2.f; } int find(int x) { return pre[x]==x ? x : pre[x]=find(pre[x]); } int kruskal() { int ans=0,fu,fv; for(int i=0;i<m;i++) { fu=find(es[i].u), fv=find(es[i].v); st.insert(es[i].u); st.insert(es[i].v); if(es[i].f==1) { pre[fu]=fv; } else if(fu!=fv) { ans+=es[i].w; pre[fu]=fv; } if(st.size()==n) break; } printf("%d\n",ans); } int main() { while(~scanf("%d",&n)) { init(); for(int i=0;i<m;i++) scanf("%d%d%d%d",&es[i].u,&es[i].v,&es[i].w,&es[i].f); sort(es,es+m,cmp); // 因为 Kruskal 算法是按照边从小到大选择 kruskal(); } return 0; }
