数学实在练不下去了,只能来水几个图论了,真想像D神一样来句:这道题很简单,直接AC就可以了。
大体思路:按照边的权值排序,枚举区间,利用并查集判断是否构成通路。
14042663 | 1395 | Slim Span | Accepted | C++ | 0.265 | 2014-08-15 02:11:53 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<list> #include<cmath> #include<string> #include<sstream> #include<ctime> using namespace std; #define _PI acos(-1.0) #define INF (1 << 10) #define esp 1e-9 typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pill; /*=========================================== ===========================================*/ #define MAXD 5000 + 10 #define MAX_SIZE 100 + 10 int fa[MAX_SIZE]; struct Line{ int x; int y; int len; friend bool operator <(Line p,Line q){ if(p.len < q.len) return true; else return false; } }node[MAXD]; int n,m; int find_father(int u){ return fa[u] == u ? u : fa[u] = find_father(fa[u]); } void init(){ for(int i = 1 ; i <= n ; i++) fa[i] = i; } bool Judge(){ int root = find_father(1); /*找到1的父亲*/ for(int i = 2 ; i <= n ; i++){ int _node = find_father(i); if(_node != root) return false; } return true; } int main(){ while(scanf("%d%d",&n,&m)){ if(!n && !m) break; for(int i = 0 ; i < m ; i++) scanf("%d%d%d",&node[i].x,&node[i].y,&node[i].len); sort(node,node + m); int ans = -1; for(int i = 0 ; i < m ; i++){ init(); for(int j = i ; j < m ; j++){ int x = node[j].x; int y = node[j].y; int _x = find_father(x); /*找到x的父亲*/ int _y = find_father(y); /*找到y的父亲*/ if(_x != _y) fa[_x] = _y; if(Judge()){ if(ans >= 0) ans = min(ans,node[j].len - node[i].len); else ans = node[j].len - node[i].len; break; } } } printf("%d\n",ans); } return 0; }
【UVA】1395-Slim Span,布布扣,bubuko.com
原文:http://blog.csdn.net/u013451221/article/details/38581095