模板題: fzu2087 統(tǒng)計(jì)樹邊
解法（mengxiang000000的博客 ）
思路：用kruskal算法模擬生成樹的過程。同時(shí)也是一個(gè)貪心生成樹的過程，我們知道，生成的樹的邊權(quán)值和是一定的，那么對于邊的替換的值也是能夠確定的：只有權(quán)值相同的邊才有可能是另一種生成樹方法的邊。
然后我就呆萌的記錄有多少重邊權(quán)值的邊，然后加上n-1，開開心心的提交，實(shí)力WA。一組數(shù)據(jù)就可以干掉我： 3 3 1 2 1 1 2 2 2 3 1
所以記得一定不要跟我犯一樣的錯(cuò)誤，我們需要的是動(dòng)態(tài)判斷一條邊權(quán)值相同的邊能否可能是另一種生成樹方法的邊。我們直接在kruskal算法過程中加上動(dòng)態(tài)判斷的成分就可以了，那么要如何判斷呢？遍歷每一條邊的時(shí)候，如果有相同權(quán)值的邊，像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); } }我們對同權(quán)值的邊判斷能否加入生成樹中，并且別忘記對邊要進(jìn)行入樹：
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,先統(tǒng)計(jì)最小生成樹的邊數(shù)，待統(tǒng)計(jì)完后再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; }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
