傳送門——BZOJCH

傳送門——Vjudge

---

設\(f_i\)表示\(i\)到\(1\)號點的最短距離，\(g_i\)表示\(i\)到\(2\)號點的最短距離，\(s_i\)表示\(n+1\)號點到\(i\)號點的最短距離，\(A=s_1,B=s_2\)

根據最短路三角形不等式，\(|f_i - A| \leq s_i \leq f_i + A , |g_i - B| \leq s_i \leq g_i + B\)

而\(s_i\)要取到最小值，所以\(s_i = \max\{|f_i - A| , |g_i - B|\}\)

所以我們要求的是\(\sum\limits_{i=1}^N \max\{|f_i - A| , |g_i - B|\}\)，這相當于求一個動點\((A,B)\)到平面上\(N\)個點\((f_i,g_i)\)的最小切比雪夫距離和。

切比雪夫距離可以轉為曼哈頓距離，將坐標\((x,y)\)變為\((\frac{x+y}{2} , \frac{x-y}{2})\)，前者的切比雪夫距離等效于后者的曼哈頓距離。而曼哈頓距離可以直接拆開橫縱坐標然后取中位數。

注意：我天真的以為2012年的題不會卡SPFA……

#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<algorithm> #include<cstring> #include<iomanip> #include<queue> #define INF 0x3f3f3f3f //This code is written by Itst using namespace std;inline int read(){int a = 0;char c = getchar();while(!isdigit(c) && c != EOF)c = getchar();while(isdigit(c)){a = a * 10 + c - 48;c = getchar();}return a; }#define PLI pair < long long , int > #define st first #define nd second const int MAXN = 1e5 + 7; struct Edge{int end , upEd , w; }Ed[MAXN * 6]; int head[MAXN] , N , M , cntEd; long long dis[2][MAXN]; priority_queue < PLI > q;inline void addEd(int a , int b , int w){Ed[++cntEd].end = b;Ed[cntEd].w = w;Ed[cntEd].upEd = head[a];head[a] = cntEd; }void SPFA(int ind){memset(dis[ind] , 0x3f , sizeof(long long) * (N + 1));dis[ind][ind + 1] = 0;q.push(PLI(0 , ind + 1));while(!q.empty()){PLI t = q.top();q.pop();if(-t.st != dis[ind][t.nd]) continue;for(int i = head[t.nd] ; i ; i = Ed[i].upEd)if(dis[ind][Ed[i].end] > dis[ind][t.nd] + Ed[i].w){dis[ind][Ed[i].end] = dis[ind][t.nd] + Ed[i].w;q.push(PLI(-dis[ind][Ed[i].end] , Ed[i].end));}} }inline long long abss(long long x){return x < 0 ? -x : x;}void out(long long a , int b){cout << a / b << '.';a %= b;for(int i = 1 ; i <= 8 ; ++i){a *= 10;cout << a / b;a %= b;}putchar('\n'); }int main(){vector < long long > x , y;for(int T = read() ; T ; --T){N = read(); M = read();memset(head , 0 , sizeof(int) * (N + 1));cntEd = 0;for(int i = 1 ; i <= M ; ++i){int a = read() , b = read() , c = read();addEd(a , b , c); addEd(b , a , c);}SPFA(0); SPFA(1);x.clear(); y.clear();long long sum = 0;for(int i = 1 ; i <= N ; ++i){x.push_back(dis[0][i] - dis[1][i]);y.push_back(dis[0][i] + dis[1][i]);}sort(x.begin() , x.end()); sort(y.begin() , y.end());long long mid = x[N >> 1];for(int i = 0 ; i < N ; ++i)sum += abss(x[i] - mid);mid = y[N >> 1];for(int i = 0 ; i < N ; ++i)sum += abss(y[i] - mid);out(sum , 2 * N);cerr << N << ' ' << sum << endl;}return 0; }

轉載于:https://www.cnblogs.com/Itst/p/10467947.html

總結

以上是生活随笔為你收集整理的BZOJ4061/Gym100624F CERC2012 Farm and Factory 最短路、切比雪夫距离的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。