SGU – 465 Fire Station Building floyd+三分

Fire Station Building floyd+三分

Source

SGU - 465

Gym - 100206B

My Solution

题意：有n个城市m条双向边，计划在一条道路上建立一个消防局，并且它离城市的距离不能小于R，每个城市i有一个发生火灾的概率pi，要求找出最优的地点，是出警需要的期望路程最小。

floyd+三分

di表示消防局和j点的最短路程，则期望的路程是 sigma{di * pi}，

所以枚举每一条可能可以设立消防局的边，然后在这个边的可行区域内进行三分，(这里二分应该是不行的，因为效果并不单调，而是呈现成凹函数)

对于当前位置x，边是(u, v)，则 di = min{x + dist[i][u], w[u][v] - x + dist[i][v]}

然后出于对浮点数的优化，p刚开始就用输入的那个万分点来算，输出的时候再除以10000，

然后这里最大的数是 (n*maxl)^2，所以会爆int，要用long long

复杂度 O(n^3 + m*n*logmaxl)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
const LL MAXN = 1e2 + 8;
const double INF = 1e18 + 8;
const double EPS = 1e-8;

LL n, g[MAXN][MAXN];
inline void floyd()
{
    LL i, j, k;
    for(k = 1; k <= n; k++){
        for(i = 1; i <= n; i++){
            for(j = 1; j <= n; j++){
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}

LL p[MAXN];
vector sons[MAXN];
inline double getsum(double s, LL u, LL v, double w)
{
    double res = 0;
    for(LL i = 1; i <= n; i++){ res += p[i] * min(s + g[i][u], w - s + g[i][v]); } return res; } int main() { freopen("fire.in", "r", stdin); freopen("fire.out", "w", stdout); #ifdef LOCAL freopen("2.txt", "r", stdin); //freopen("fire.out", "w", stdout); LL T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); LL m, R, u, v, i, j, sz; cin >> n >> m >> R;
    for(i = 1; i <= n; i++){ cin >> p[i];
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){ g[i][j] = INF; if(i == j) g[i][j] = 0; } } while(m && m--){ cin >> u >> v;
        cin >> g[u][v];
        g[v][u] = g[u][v];
        sons[u].push_back(ii(v, g[u][v]));
    }
    floyd();
    double l, r, ll, rr, ans = INF, ans1, ans2;
    for(i = 1; i <= n; i++){
        sz = sons[i].size();
        for(j = 0; j < sz; j++){ if(sons[i][j].second >= 2 * R){
                l = R, r = sons[i][j].second - R;
                ans = min(ans, getsum(l, i, sons[i][j].first, sons[i][j].second));
                ans = min(ans, getsum(r, i, sons[i][j].first, sons[i][j].second));
                while(l + EPS < r){ ll = l + (r - l) / 3; rr = r - (r - l) / 3; ans1 = getsum(ll, i, sons[i][j].first, sons[i][j].second); ans2 = getsum(rr, i, sons[i][j].first, sons[i][j].second); if(ans1 > ans2){
                        l = ll;
                    }
                    else r = rr;
                    ans = min(ans, min(ans1, ans2));
                }

            }
        }
    }
    for(i = 1; i <= n; i++){
        for(j = 1; j <= n; j++){ if(g[i][j] >= INF){ ans = INF; break; }
        }
    }
    if(n == 1 && R == 0) cout << 0 << endl;
    else if(fabs(ans - INF) < EPS) cout << -1 << endl;
    else cout << fixed << setprecision(5) << ans / 10000 << endl;

    #ifdef LOCAL
    for(i = 1; i <= n; i++) sons[i].clear();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx