模板題: fzu2087 統計樹邊
解法（mengxiang000000的博客 ）
思路：用kruskal算法模擬生成樹的過程。同時也是一個貪心生成樹的過程，我們知道，生成的樹的邊權值和是一定的，那么對于邊的替換的值也是能夠確定的：只有權值相同的邊才有可能是另一種生成樹方法的邊。
然后我就呆萌的記錄有多少重邊權值的邊，然后加上n-1，開開心心的提交，實力WA。一組數據就可以干掉我： 3 3 1 2 1 1 2 2 2 3 1
所以記得一定不要跟我犯一樣的錯誤，我們需要的是動態判斷一條邊權值相同的邊能否可能是另一種生成樹方法的邊。我們直接在kruskal算法過程中加上動態判斷的成分就可以了，那么要如何判斷呢？遍歷每一條邊的時候，如果有相同權值的邊，像kruskal一樣的判斷條件，判斷這條邊能否加入生成樹中即可。
kruskal算法判斷一條邊是否能夠貪心的加入生成樹中：
for(int i=0;i<m;i++) { if(find(a[i].x)!=find(a[i].y)) { zhongquanzhi+=a[i].w; merge(a[i].x,a[i].y); } }我們對同權值的邊判斷能否加入生成樹中，并且別忘記對邊要進行入樹：
for(int i=0;i<m;i=j) { for(j=i;a[i].w==a[j].w;j++) { if(find(a[j].x)!=find(a[j].y)) { output++; } } for(j=i;a[i].w==a[j].w;j++) { if(find(a[j].x)!=find(a[j].y)) { merge(a[j].x,a[j].y); } } }簡而言之 如果安全，則先不Union,先統計最小生成樹的邊數，待統計完后再Union; poj1679 與此題類似
fzu2087
#include<iostream>#include<algorithm>using namespace std;const int maxn=100005;typedef struct node{ int st,ed,cost;}Edge ;Edge edge[100005];int cmp(Edge a,Edge b){ return a.cost<b.cost;}int fa[maxn];void init(){ for(int i=0;i<maxn;i++) fa[i]= i;}int Find(int x){ if(fa[x] == x) return fa[x]; else return fa[x] = Find(fa[x]);}void Union(int x,int y){ int fx=Find(x),fy=Find(y); if(fx!= fy) fa[fx] = fy;}int main(){ ios_base::sync_with_stdio(false); int T; cin>>T; while(T--){ int n,m,t1,t2,t3; cin>>n>>m; for(int i=0;i<m;i++){ cin>>t1>>t2>>t3; edge[i].st=t1,edge[i].ed=t2,edge[i].cost=t3; } sort(edge,edge+m,cmp); int bianshu=0; int tot_cost = 0; init(); for(int i=0;i < m ;i++){ for(int j=i;edge[j].cost == edge[i].cost;j++) if(Find(edge[j].st)!= Find(edge[j].ed)) bianshu++; for(int j=i;edge[j].cost == edge[i].cost;j++) if(Find(edge[j].st)!= Find(edge[j].ed) ) Union(edge[j].st,edge[j].ed),tot_cost+=edge[j].cost; } cout<<bianshu<<endl; }}新聞熱點
疑難解答
