[ codeforces ] 2014 ACM-ICPC Asia Tokyo Regional Contest Problem F 最小生成樹上的必然邊

題目:
http://codeforces.com/gym/100803
給一張圖，找出一些邊，在這張圖的所有最小生成樹中一定會包含它
輸出這些邊的各數及權值總和

解法:
先找出一顆最小生成樹，根據迴路性質，這棵樹上插入其他原本不再最小生成樹上的邊，會形成一個環，刪除環上任意一個與原本插入的邊權值相同的邊，那這顆新產生的樹依然是最小生成樹。因此把每條不再最小生成樹上的邊都檢查一遍，如果會造成某些樹上的邊有機會被刪除，就把這條邊標記，最後剩下沒被標記的邊就是滿足題目要求的邊。

code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

#include<bits/stdc++.h> using namespace std; struct P{ bool is; int a,b,c; P():is(0),a(0),b(0),c(0){} inline const bool operator<(const P&B)const{ return c<B.c; } }s[50005]; int n,m; vector<int >G[505]; int pa[505],dep[505]; int st[505],mp[505][505]; int ans,add; void dfs(int x){ for(vector<int >::iterator i=G[x].begin();i!=G[x].end();++i){ if(*i==pa[x])continue; pa[*i]=x; dep[*i]=dep[x]+1; dfs(*i); } } int find(int x){ return st[x]==x?x:st[x]=find(st[x]); } inline void uion(int a,int b){ st[find(a)]=find(b); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i)st[i]=i; for(int i=0;i<m;++i){ scanf("%d%d%d",&s[i].a,&s[i].b,&s[i].c); } sort(s,s+m); for(int i=0;i<m;++i){ if(find(s[i].a)==find(s[i].b)){ s[i].is=1; }else{ uion(s[i].a,s[i].b); ++add; ans+=s[i].c; mp[s[i].a][s[i].b]=s[i].c; mp[s[i].b][s[i].a]=s[i].c; G[s[i].a].push_back(s[i].b); G[s[i].b].push_back(s[i].a); } } dfs(1); for(int i=0;i<m;++i){ if(s[i].is){ int a=s[i].a,b=s[i].b; if(dep[a]<dep[b])swap(a,b); while(dep[a]>dep[b]){ if(mp[a][pa[a]]==s[i].c){ --add; ans-=s[i].c; mp[a][pa[a]]=mp[pa[a]][a]=0; } a=pa[a]; } while(a!=b){ if(mp[a][pa[a]]==s[i].c){ --add; ans-=s[i].c; mp[a][pa[a]]=mp[pa[a]][a]=0; } a=pa[a]; if(mp[b][pa[b]]==s[i].c){ --add; ans-=s[i].c; mp[b][pa[b]]=mp[pa[b]][b]=0; } b=pa[b]; } } } printf("%d %d\n",add,ans); return 0; }