最小生成树。每次加一条边之后判断一下集合是否符合条件即可。
#include<iostream> #include<string> #include<cstdio> #include<set> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; //ifstream cin; const int maxn = 5010,INF = 0x3f3f3f3f; int n,m; struct node{ int u,v,w; bool operator < (const node &a) const{ return w > a.w; } }; vector<node> e; vector<pair<int,int>> r[maxn]; int fa[maxn]; int son[maxn]; int find(int x){ if (x == fa[x]) return x; else return fa[x] = find(fa[x]); } bool check(int x){ int mi = INF,mx = 0; for(int u = 1;u <= n;++u){ if (find(u) == x){ for(int i = 0;i < r[u].size();++i){ int p = r[u][i].first,w = r[u][i].second; if (find(p) == x){ mi = min(mi,w); } else{ mx = max(mx,w); } if (mi <= mx) return false; } } } return true; } void kruskal(){ int ans = 0; for(int i = 1;i <= n;++i){ fa[i] = i; son[i] = 1; } for(int k = 0;k < m;++k){ int u = e[k].u,v = e[k].v; u = find(u),v = find(v); if (u != v){ fa[u] = v; son[v] += son[u]; if (check(v)){ ans += son[v]; } } } printf("%d\n",ans); } void init(){ cin >> n >> m; int a,b,w; e.clear(); for(int i = 1;i <= n;++i) r[i].clear(); for(int i = 0;i < m;++i){ cin >> a >> b >> w; e.push_back({a,b,w}); r[a].push_back({b,w}); r[b].push_back({a,w}); } sort(e.begin(),e.end()); kruskal(); } int main(){ //cin.open("in.txt"); int t; cin >> t; while(t--){ init(); } }