设为首页 加入收藏

TOP

USACO cowtour Floyd + 枚举
2015-07-20 18:06:18 来源: 作者: 【大 中 小】 浏览:3次
Tags：USACO cowtour Floyd 枚举

给出来的数据量还是可以的。题意：有若干个牧场，至少有两个不连通，一个牧场的直径就是牧场中最远的两个牧区的距离。要求找出几个牧场中最短的直径，就是找一条路径连接几个牧区，使这个直径最终最小。

基本方法，把整个图根据输入划分成几个不连通的牧区，然后求出每个牧区的直径（即每个连通块中的最长路径），然后枚举两个不在同一牧区的点，设blocks[i]记录第i个节点所在连通块的直径，那么result = min(blocks[i] + dis(i, j) + blocks[j]),可以用并查级判断两个点是否连通


/*
ID:kevin_s1
PROG:cowtour
LANG:C++
*/

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
        #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              using namespace std; #define MAXN 175 const double INF = 1E15; //gobal variable==== int N; struct point{ double x; double y; }points[MAXN]; double Graph[MAXN][MAXN]; double result; int Father[MAXN]; int Rank[MAXN]; double blocks[MAXN]; //================== //function========== int Find(int x){ while(x != Father[x]){ x = Father[x]; } return x; } bool check(int x, int y){ x = Find(x); y = Find(y); if(x == y) return true; else return false; } void Union(int x, int y){ x = Find(x); y = Find(y); if(x == y) return; if(Rank[x] >= Rank[y]){ Father[y] = x; Rank[x] += Rank[y]; } else{ Father[x] = y; Rank[y] += Rank[x]; } } double dist(point start, point end){ return sqrt((end.x - start.x)*(end.x - start.x) + (end.y - start.y)*(end.y - start.y)); } void Input(){ cin>>N; for(int i = 1; i <= N; i++){ cin>>points[i].x>>points[i].y; blocks[i] = -1; Father[i] = i; Rank[i] = 1; } char flg; for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++){ cin>>flg; if(i == j) Graph[i][j] = 0; else if(flg == '1'){ Union(i, j); Graph[i][j] = dist(points[i], points[j]); } else if(flg == '0') Graph[i][j] = INF; } } void Floyd(){ for(int k = 1; k <= N; k++){ for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ if(k == i || k == j) continue; if(Graph[i][j] > Graph[i][k] + Graph[k][j]){ Graph[i][j] = Graph[i][k] + Graph[k][j]; } } } } } void print(){ for(int i = 1; i <= N; i++){ for(int j = 1; j <= N; j++){ cout<
             
               result) result = blocks[i]; printf("%.6lf\n", result); return 0; }


【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：[ACM] POJ 2442 Sequence (堆的性.. 下一篇：POJ 1159 Palindrome DP

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: