最小生成树C代码

题意：求从1到2的路径中，使得最长路尽量小。
细节参见代码：
#include<cstdio>  #include<cstring>  #include<algorithm>  #include<iostream>  #include<string>  #include<vector>  #include<stack>  #include<bitset>  #include<cstdlib>  #include<cmath>  #include<set>  #include<list>  #include<deque>  #include<map>  #include<queue>  #define Max(a,b) ((a)>(b)?(a):(b))  #define Min(a,b) ((a)<(b)?(a):(b))  using namespace std;  typedef long long ll;  typedef long double ld;  const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;  const int mod = 1000000000 + 7;  const int INF = int(1e9);  // & 0x7FFFFFFF  const int seed = 131;  const ll INF64 = ll(1e18);  const int maxn = 200 + 10;  int T,n,m,cnt,p[maxn],kase=0;  double ans[maxn][maxn],x[maxn],y[maxn];  struct node {      int a, b;      double dist;      node(int a=0, int b=0, double dist=0):a(a), b(b), dist(dist) {}      bool operator < (const node& rhs) const {          return dist < rhs.dist;      }  }a[maxn*maxn];  vector<node> g[maxn];  int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); }  void dfs(int u, int fa) {      int len = g[u].size();      for(int i=0;i<len;i++) {          int v = g[u][i].a;          if(v != fa) {              ans[1][v] = max(ans[1][u], g[u][i].dist);              dfs(v, u);          }      }  }  double solve() {      for(int i=1;i<=n;i++) p[i] = i, g[i].clear();      sort(a, a+cnt);      for(int i=0;i<cnt;i++) {          int x = _find(a[i].a);          int y = _find(a[i].b);          if(x != y) {              p[x] = y;              g[a[i].a].push_back(node(a[i].b, 0, a[i].dist));              g[a[i].b].push_back(node(a[i].a, 0, a[i].dist));          }      }      ans[1][1] = -1.0;      dfs(1, 1);      return ans[1][2];  }  int main() {      while(~scanf("%d",&n) && n) {          for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);          cnt = 0;          for(int i=1;i<=n;i++) {              for(int j=i+1;j<=n;j++) {                  double cur = sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] - y[j])*(y[i] - y[j]));                  a[cnt++] = node(i,j,cur);              }          }          printf("Scenario #%d\n",++kase);          printf("Frog Distance = %.3f\n\n",solve());      }      return 0;  }
热门搜索

最小生成树C代码
