testA

 

输入文件: testA.in  输出文件testA.out 时限2000ms

 

问题描述：

 

        有一个城市拥有N个节点，被M条有权无向路径连接。现在你要在一个地方(可以在路径上当然也可以在节点上)开设一家咖啡馆，使得所有节点达到这个咖啡馆的最短路里面最大值最小（也就是说离咖啡馆最远的节点距离尽可能得小），求出这个最大值的最小值。

 

 

输入描述：

第一行N和M。

第2至M+1行，每行三个整数U,V,W。表示从U到V有一条权值为W的无向边。

 

输出描述：

一行一个数表示答案。 四舍五入至2位小数

 

数据范围 N<=200 , W<=100000 , M<=19900

 

样例输入：

3 2

1 2 100

2 3 1

 

样例输出：

50.50

　　

 

 

由于可以取边上的点 于是毫无头绪 写的最小生成树之后取最长边/2 竟然有20分-_-

解题报告也没有看懂

解题报告：

　　　　

　　注意这道题可以选在边上进行咖啡馆的选择。

　　要找出一个最小距离的点不是很容易,但是判断一个答案是否是合法的可以迅速解决。

　　假设答案是L

　　我们枚举一条边(x,y,w),判断在这条边上建立咖啡馆是否合法。

 

　　那么从一个点k到达咖啡馆有两种选择

　　(1)  k->x->咖啡馆  (2)  k->y->咖啡馆

　　设l = L-d[x][y] , r = L-d[y][k]

　　那么当l<0 并且r<0时肯定不能在这条边上建立咖啡馆

　　当l>=w或者r>=w时 或者 l+r >= w 时 一定合法

     　　否则 要么在x->y的路径的l长度之内建立咖啡馆或者在y->x的路径的长度r之内建立咖啡馆。

　　那么从l+0.5到w-r-0.5这段区间对于k来说并不合法。

　　对于每个点k求出这样的区间，如果他们的并是整个区间[0,w]，则这条边不能建立咖啡馆。

 

　　对于L来说只要有一条边上可以满足条件则满足条件。

 

　　二分L再进行判断。复杂度是O(30MN)。 最后的结果肯定是整数或者是整数+0.5。所以先对所有边*2避免小数运算。

 

 

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 #define INF 0x3f3f3f 7 #define N 220 8  9 struct edges {10     int v,l;11 };12 struct interval {13     int left,right;14 };15     16 vector 
          
            edge[N];17 int n,m;18 int dis[N][N];19 20 bool cmp(interval a,interval b) {21     if (a.left==b.left) return a.right
           
             v;27 for (int i=1;i<=n;i++) {28 for (int j=0;j
            
             =w || r>=w) continue;37 if (l+r>=w) continue;38 if (l==-1 && r==-1) break;39 interval vv;40 vv.left=l+1; vv.right=w-r-1;41 v.push_back(vv);42 }43 if (k==n+1) {44 if (v.empty()) return true;45 sort(v.begin(),v.end(),cmp);46 int last=0;47 for (int t=0;t
             
              last) last=v[t].right+1;50 }51 }52 }53 }54 return false;55 }56 57 58 void solve() {59 int l=0,r=INF;60 int ans;61 while (l<=r) {62 int mid=(l+r)/2;63 if (check(mid)) {64 ans=mid;65 r=mid-1;66 }67 else {68 l=mid+1;69 }70 }71 printf("%.2f",double(ans)/2.0);72 }73 74 int main() {75 memset(dis,INF,sizeof(dis));76 scanf("%d%d",&n,&m);77 for (int i=1;i<=n;i++) dis[i][i]=0;78 for (int i=0;i