TopCoder SRM 710 Div2 Hard MinMaxMax Floyd最短路变形

题意：

有一个无向连通图，没有重边没有自环，并给出顶点的权值和边的权值

定义一条路径\(difficulty\)值为该路径上最大的点权乘上最大的边权

定义函数\(d(i,j)\)为\(i,j\)之间的所有中路径最小的\(difficulty\)值

求\(\sum_{i<j}d(i,j)\)

分析：

令\(minw(i,j)\)表示\(i,j\)之间的路径中最大边权的最小值

按照点权从小到大枚举点\(k\)，然后按照Floyd算法那样逐个去更新：

\[minw(i,j)=min(minw(i,j), max(minw(i,k), minw(k,j)))
\]

\[d(i,j)=min(d(i,j),minw(i,j) \cdot max(v_i, v_j, v_k))
\]

#define REP(i, a, b) for(int i = a; i < b; i++)

#define SZ(a) ((int)a.size())

#define ALL(a) a.begin(), a.end()

typedef long long LL;

const LL INF = 1LL << 60;

typedef pair<int, int> PII;

const int maxn = 300 + 10;

LL minw[maxn][maxn], ans[maxn][maxn];

vector<PII> vertex;

class MinMaxMax {

    public:

    long long findMin(vector<int> a, vector<int> b, vector<int> w, vector<int> v) {

        int n = SZ(v), m = SZ(a);

        REP(i, 0, n) REP(j, 0, n) minw[i][j] = ans[i][j] = INF;

        REP(i, 0, m) minw[a[i]][b[i]] = minw[b[i]][a[i]] = w[i];

        REP(i, 0, n) vertex.emplace_back(v[i], i);

        sort(ALL(vertex));

        for(PII x : vertex) {

            int k = x.second;

            REP(i, 0, n) REP(j, 0, n) if(i != j) {

                minw[i][j] = min(minw[i][j], max(minw[i][k], minw[k][j]));

                if(minw[i][j] == INF) continue;

                ans[i][j] = min(ans[i][j], minw[i][j] * max(v[i], max(v[j], v[k])));

            }

        }

        LL res = 0;

        REP(i, 0, n) REP(j, 0, i) res += ans[i][j];

        return res;

    }

};