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 <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 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 <edges> 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<b.right; 22 return a.left<b.left; 23 } 24 25 bool check(int L) { 26 vector <interval> v; 27 for (int i=1;i<=n;i++) { 28 for (int j=0;j<edge[i].size();j++) { 29 v.clear(); 30 int x=i, y=edge[i][j].v, w=edge[i][j].l, k; 31 for (k=1;k<=n;k++) { 32 int l=L-dis[x][k]; 33 int r=L-dis[y][k]; 34 if (l<0) l=-1; 35 if (r<0) r=-1; 36 if (l>=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<v.size();t++) { 48 if (last<v[t].left) return true; 49 if (v[t].right+1>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<m;i++) { 79 int u,v,l; 80 edges e; 81 scanf("%d%d%d",&u,&v,&l); 82 l=l*2; 83 e.v=v; e.l=l; 84 edge[u].push_back(e); 85 dis[v][u]=dis[u][v]=min(dis[v][u],l); 86 } 87 88 for (int k=1;k<=n;k++) { 89 for (int i=1;i<=n;i++) { 90 for (int j=1;j<=n;j++) { 91 dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]); 92 } 93 } 94 } 95 96 solve(); 97 }