亚洲香蕉成人av网站在线观看_欧美精品成人91久久久久久久_久久久久久久久久久亚洲_热久久视久久精品18亚洲精品_国产精自产拍久久久久久_亚洲色图国产精品_91精品国产网站_中文字幕欧美日韩精品_国产精品久久久久久亚洲调教_国产精品久久一区_性夜试看影院91社区_97在线观看视频国产_68精品久久久久久欧美_欧美精品在线观看_国产精品一区二区久久精品_欧美老女人bb

首頁 > 學院 > 開發設計 > 正文

POJ 3522 Slim Span

2019-11-14 11:36:15
字體：大 中 小
來源：轉載
供稿：網友

2017寒假集訓 3-G

POJ 3522 Slim Span

kruskal生成樹

傳送門：HUSTOJ

傳送門：POJ

題意

圖，求生成樹，使得樹內最大權邊與最小權邊差最小。

思路

又是一道以前看過沒寫的題。。不過這題比較簡單，就當是留一下kruskal的板子。

要求生成樹最大權最小權差最小，那么邊要先排序，就想到了kruskal。kruskal選取方式是貪心，所以最小邊確定了后最大邊必然確定，而kruskal選出來的那個最大邊的權一定會盡可能的小。

到現在思路就很明確了，枚舉最小邊。判斷剩下的邊能不能成為生成樹，如果能，記錄第一條加入的邊與第n-1條加入的邊(對應最大權邊與最小權邊)權差。

代碼

#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>#include<string>#include<cstring>#include<vector>#include<cmath>#include<queue>using namespace std;const int MAXN=107;const int MAXM=5007;const int oo=0x3f3f3f3f;typedef long long LL;const LL loo=4223372036854775807ll;int father[MAXN];void init(int n){ for(int i=1; i<=n; i++) { father[i]=i; }}int find(int x){ if(father[x]==x) return x; else { return father[x]=find(father[x]); }}void merge(int x, int y){ int fx=father[x], fy=father[y]; if(fx!=fy) father[fx]=fy;}struct edge{ int from, to, cost; edge(){} edge(int a, int b, int c){ from=a;to=b;cost=c; }};bool cmp(edge a, edge b){ return a.cost<b.cost;}edge e[MAXM];int main(){ int n, m; while(cin>>n>>m&&(n!=0)) { memset(e, 0, sizeof(e)); for(int i=0;i<m;i++) { scanf("%d%d%d", &e[i].from, &e[i].to, &e[i].cost); } sort(e, e+m,cmp); int res=oo; for(int i=0;i<=m-n+1;i++) { int tres=e[i].cost; init(n+1); int cnt=0; for(int j=i;j<m;j++) { edge te=e[j]; if(find(te.from)!=find(te.to)) { merge(te.from, te.to); cnt++; } if(cnt==n-1) { tres=e[j].cost-tres; break; } } if(cnt==n-1) res=min(res, tres); } cout<<(res>=oo ? -1 : res)<<endl; } //system("pause"); return 0;}

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
亚洲香蕉成人av网站在线观看_欧美精品成人91久久久久久久_久久久久久久久久久亚洲_热久久视久久精品18亚洲精品_国产精自产拍久久久久久_亚洲色图国产精品_91精品国产网站_中文字幕欧美日韩精品_国产精品久久久久久亚洲调教_国产精品久久一区_性夜试看影院91社区_97在线观看视频国产_68精品久久久久久欧美_欧美精品在线观看_国产精品一区二区久久精品_欧美老女人bb
亚洲午夜未删减在线观看| 国产91ⅴ在线精品免费观看| 欧美性生交大片免网| 九九热视频这里只有精品| 狠狠色狠狠色综合日日五| 欧美午夜精品久久久久久久| 国产精品永久免费在线| 国产91热爆ts人妖在线| 亚洲激情免费观看| 国产999精品| 精品国产乱码久久久久久天美| 国产成人极品视频| 欧美成人亚洲成人| 在线观看国产精品日韩av| 成人在线免费观看视视频| 欧美中文在线视频| 国产91在线高潮白浆在线观看| 亚洲夜晚福利在线观看| 色琪琪综合男人的天堂aⅴ视频| 国产精品入口免费视频一| 国产精品免费看久久久香蕉| 国产精品成人v| 色偷偷888欧美精品久久久| 在线看福利67194| 亚洲人成在线播放| 51精品在线观看| 亚洲色图在线观看| 亚洲国产欧美一区二区三区同亚洲| 色噜噜亚洲精品中文字幕| 久久久久久久久爱| 欧美黄色www| 91精品国产综合久久香蕉| 51ⅴ精品国产91久久久久久| 国产亚洲激情视频在线| 久久久久久久久久亚洲| 亚洲男人天堂手机在线| 国产精品视频色| 国产免费一区二区三区在线观看| 亚洲精品国产综合区久久久久久久| 一区二区三区在线播放欧美| 久久亚洲精品国产亚洲老地址| 国产一区私人高清影院| 欧美日韩在线影院| 亚洲japanese制服美女| 精品久久久久久久久久| 国产精品一二区| 国产精品v片在线观看不卡| 亚洲成人aaa| 57pao成人国产永久免费| 深夜福利91大全| 午夜精品蜜臀一区二区三区免费| 国产亚洲欧美日韩精品| 久久久精品视频在线观看| 欧美一区二三区| 久久久久久久久久久av| 国产精品一区二区久久国产| 欧美色视频日本高清在线观看| 91夜夜揉人人捏人人添红杏| 亚洲欧美激情一区| 亚洲黄一区二区| 亚洲另类欧美自拍| 91久久精品日日躁夜夜躁国产| 色噜噜狠狠狠综合曰曰曰88av| 毛片精品免费在线观看| 日本午夜精品理论片a级appf发布| 久久久精品一区二区| 欧美亚洲成人精品| 亚洲成人av资源网| 久久天天躁狠狠躁夜夜av| 国产精品视频男人的天堂| 久久色免费在线视频| 亚洲国产精品va| 国内精品视频在线| 91精品国产沙发| 亚洲自拍偷拍色片视频| 国产精品午夜视频| 亚洲三级黄色在线观看| 91精品啪aⅴ在线观看国产| 久久久久久久影视| 成人国产精品av| 中文字幕日韩专区| 69久久夜色精品国产7777| 国产精品v片在线观看不卡| 91在线精品视频| 精品亚洲精品福利线在观看| 一区二区三区美女xx视频| 欧美—级a级欧美特级ar全黄| 国产香蕉精品视频一区二区三区| 韩国国内大量揄拍精品视频| www.久久久久| 欧美亚洲第一区| 国产精品h在线观看| 久久久女女女女999久久| 97在线免费观看视频| 中文字幕少妇一区二区三区| 欧美高清一级大片| 国产精品入口尤物| 国产午夜精品免费一区二区三区| 成人黄色av播放免费| 国产精品直播网红| 色爱av美腿丝袜综合粉嫩av| 国产成人高清激情视频在线观看| 日本亚洲欧美成人| 中国日韩欧美久久久久久久久| 日韩欧美在线视频免费观看| 色av中文字幕一区| 欧美视频专区一二在线观看| 国产精品久久久久久久久久小说| 欧美在线www| 国产xxx69麻豆国语对白| 国产91免费观看| 亚洲电影免费观看高清| 亚洲精品福利在线观看| 亚洲性xxxx| 成人观看高清在线观看免费| 亚洲第一综合天堂另类专| 欧美特黄级在线| 国产精品v日韩精品| 992tv成人免费视频| 欧美xxxx14xxxxx性爽| 亚洲精品www久久久久久广东| 自拍偷拍亚洲在线| 日韩av手机在线| 欧美肥老太性生活视频| 欧美电影免费观看高清| 欧美激情乱人伦一区| 国产精品久久久久久亚洲调教| 国产欧美一区二区三区久久| 日韩国产精品亚洲а∨天堂免| 成人羞羞国产免费| 国产亚洲一级高清| 岛国av午夜精品| 九九热99久久久国产盗摄| 成人妇女免费播放久久久| 色综合91久久精品中文字幕| 久久久久久久久电影| 国产亚洲精品美女| 亚洲国产成人精品久久| 久久久99久久精品女同性| 97视频免费在线观看| 91美女片黄在线观| 欧美激情精品久久久久久大尺度| 国产精品视频地址| 欧美小视频在线观看| 欧美黑人巨大xxx极品| 久久91亚洲精品中文字幕| 亚州国产精品久久久| 日韩高清不卡av| 欧美性极品少妇精品网站| 欧美丰满老妇厨房牲生活| 国内伊人久久久久久网站视频| 欧美性猛交xxxx偷拍洗澡| 国产亚洲a∨片在线观看| 97色在线播放视频| 色av吧综合网| 国产精品嫩草视频| 欧美日韩国产成人在线| 中文字幕日韩高清| 久久久精品视频成人| 色综合色综合久久综合频道88| 中文字幕在线看视频国产欧美在线看完整| 色妞色视频一区二区三区四区| 亚洲国产精品99| 亚洲美女视频网|