最小生成树C代码

gjwin的头像 gjwin 0 2016-03-05 10:58 0

 基本信息

× 1    × 1    浏览数: 33334 分享时间: 2 年 前
4
题目链接:点击打开链接 题意:求从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; }


12 [下一页]
  • anasilvabr的头像 anasilvabr 2018-05-09 07:35 代码数:0
    Valuable information. Thank you for always posting quality content. Curso de Excel Completo
  • ossaa的头像 ossaa 2018-05-09 16:46 代码数:0
    This is such a great resource that you are providing and you give it away for free. cryptocurrency converter calculator
  • ossaa的头像 ossaa 2018-05-10 19:23 代码数:0
    This is such a great resource that you are providing and you give it away for free. I love seeing websites that understand the value of providing a quality resource for free. It is the old what goes around comes around routine. new business ideas in india
  • ossaa的头像 ossaa 2018-05-16 20:00 代码数:0
    I recently came across your blog and have been reading along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often. SEO Company
  • hellojukay的头像 hellojukay 2016-07-12 12:48 代码数:0
    这是c++代码
  • gererik的头像 gererik 2018-04-21 14:21 代码数:0
    Thanks  for another wonderful post. Where else could anybody get that type of info in such an ideal way of writing? ninja logo
  • gererik的头像 gererik 2018-04-21 15:34 代码数:0
    Keep up the good  work , I read few posts  on this  web site  and I  conceive that your blog  is very   interesting and has   sets  of  fantastic   information. refrigerator repair service near me
  • herenzi的头像 herenzi 2017-07-15 00:17 代码数:0
    一次性包含这么多头文件,用到了几个?
  • 认识你自己的头像 认识你自己 2017-07-25 21:40 代码数:0
    66666
  • gererik的头像 gererik 2018-04-23 16:49 代码数:0
    This is such a great resource that you are providing and you give it away for free. community   community
您的评论: