题意分析

金刚是特兰西瓦尼亚的统治者，拥有G名士兵。王国由两座城市（邮编95050和104729）和N个城镇（邮编0到N-1）组成，部分城镇间有双向道路。金刚需要在一些道路上部署士兵，使得：

从城市95050到城市104729的每条路径都至少经过一名士兵（即士兵部署形成割）。

当任意一座城市被攻击时，所有士兵都能快速集结到被攻击城市，且集结时间（即所有士兵中到达被攻击城市的最长时间）最小化。

士兵只能部署在道路上（不能在城市或城镇内），同一条道路可部署多名士兵。目标是找到最小集结时间T，并输出（保留一位小数）。如果无法用G名士兵阻断所有路径，输出"Impossible"。

解题思路

士兵部署需形成从城市95050到104729的割，即删除部署士兵的边后，两个城市不连通。 边(u,v)在时间T内可用的条件是：存在x∈[0,w]使得士兵在T时间内能到达两个城市。该条件等价于以下四个条件之一：

$(d0[u] ≤ T 且 d1[u] ≤ T)$ // 部署在u端

$(d0[v] ≤ T 且 d1[v] ≤ T)$ // 部署在v端

$(d0[u] ≤ T 且 d1[v] ≤ T 且 d0[u] + d1[v] + w ≤ 2T) // 部署在中间位置（u→v方向）$

$(d0[v] ≤ T 且 d1[u] ≤ T 且 d0[v] + d1[u] + w ≤ 2T) // 部署在中间位置（v→u方向）$

标程

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <tuple>
#include <climits>

using namespace std;

const int INF = 400000; // 大于最大G(353535)

// Dinic算法实现网络流
struct Edge {
    int v, cap, rev;
    Edge(int v, int cap, int rev) : v(v), cap(cap), rev(rev) {}
};

class Dinic {
public:
    int n;
    vector<vector<Edge>> graph;
    vector<int> level, iter;

    Dinic(int n) {
        this->n = n;
        graph.resize(n);
        level.resize(n);
        iter.resize(n);
    }

    void addEdge(int u, int v, int cap) {
        graph[u].emplace_back(v, cap, graph[v].size());
        graph[v].emplace_back(u, 0, graph[u].size()-1);
    }

    void bfs(int s) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto &e : graph[u]) {
                if (e.cap > 0 && level[e.v] == -1) {
                    level[e.v] = level[u] + 1;
                    q.push(e.v);
                }
            }
        }
    }

    int dfs(int u, int t, int f) {
        if (u == t) return f;
        for (int &i = iter[u]; i < graph[u].size(); i++) {
            Edge &e = graph[u][i];
            if (e.cap > 0 && level[u] < level[e.v]) {
                int d = dfs(e.v, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    graph[e.v][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int maxFlow(int s, int t) {
        int flow = 0;
        while (true) {
            bfs(s);
            if (level[t] == -1) break;
            fill(iter.begin(), iter.end(), 0);
            int f;
            while ((f = dfs(s, t, INT_MAX)) > 0) {
                flow += f;
            }
        }
        return flow;
    }
};

// Dijkstra计算单源最短路径
void dijkstra(int start, vector<vector<pair<int, int>>> &graph, vector<int> &dist) {
    int n = graph.size();
    dist.assign(n, INF);
    dist[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    while (!pq.empty()) {
        int d = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if (d != dist[u]) continue;
        for (auto &e : graph[u]) {
            int v = e.first;
            int w = e.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    while (cin >> N, N) {
        int G, E;
        cin >> G >> E;
        int n = N + 2; // 节点数：城市0(0), 城市1(1), 城镇0~N-1(2~n-1)
        vector<vector<pair<int, int>>> graph(n); // 原图
        vector<tuple<int, int, int>> edges; // 存储边(u, v, w)

        for (int i = 0; i < E; i++) {
            int a, b, w;
            cin >> a >> b >> w;
            int u, v;
            if (a == 95050) u = 0;
            else if (a == 104729) u = 1;
            else u = a + 2;

            if (b == 95050) v = 0;
            else if (b == 104729) v = 1;
            else v = b + 2;

            graph[u].emplace_back(v, w);
            graph[v].emplace_back(u, w);
            edges.emplace_back(u, v, w);
        }

        vector<int> d0(n, INF), d1(n, INF);
        dijkstra(0, graph, d0);
        dijkstra(1, graph, d1);

        double low = 0.0, high = 400000.0, ans = high;
        bool possible = false;
        const double eps = 1e-4;
        while (high - low > eps) {
            double mid = (low + high) / 2.0;
            Dinic dinic(n);

            for (auto &e : edges) {
                int u = get<0>(e), v = get<1>(e), w = get<2>(e);
                bool usable = false;
                if ((d0[u] <= mid && d1[u] <= mid) ||
                    (d0[v] <= mid && d1[v] <= mid) ||
                    (d0[u] <= mid && d1[v] <= mid && d0[u] + d1[v] + w <= 2*mid) ||
                    (d0[v] <= mid && d1[u] <= mid && d0[v] + d1[u] + w <= 2*mid)) {
                    usable = true;
                }

                if (usable) {
                    dinic.addEdge(u, v, 1);
                    dinic.addEdge(v, u, 1);
                } else {
                    dinic.addEdge(u, v, INF);
                    dinic.addEdge(v, u, INF);
                }
            }

            int min_cut = dinic.maxFlow(0, 1);
            if (min_cut <= G) {
                high = mid;
                ans = mid;
                possible = true;
            } else {
                low = mid;
            }
        }

        if (possible) {
            cout << fixed << setprecision(1) << ans << "\n";
        } else {
            cout << "Impossible\n";
        }
    }
    return 0;
}