UVa1311/LA2666 Servers

题目链接

   本题是2002年icpc欧洲区域赛中欧赛区和西南欧赛区的题目

题意

   有n（1 ≤ n ≤ 30000）台服务器，通过m（1 ≤ m ≤ 5n）条网线相连，每个服务器最多与10台其他服务器相连并且任意两台相互连通，给出每台服务器的排名$r_i$以及每条网线两端连接的服务器a、b和传输时间t（1 ≤ t ≤ 1000, 1 ≤ a, b ≤ n, a ≠ b）。定义定义服务器V和W间的距离δ(V,W)为V和W间的最短传输时间，并且δ(V,V)=0。对δ(V,U) ≤ δ(V,W) 的每个服务器U都有r(U) ≤ r(W)时V需要存储W的信息。请计算整个服务器网络需要存储的信息总量。

分析

   先说一个从uDebug上看到的坑点：UVa上的输入输出格式和题目描述不相同，输入的第一行是测试case总条数，然后每个case的输入才是题目交代的格式，并且相邻两个case的输出之间要空一行。

   本题其实是Dijkstra加一点优化，可将复杂度优化到$O(ans\log n)$，但仍然可以出卡$O(n^2\log n)$的数据导致tle。说一下优化方法：对服务器按rank从大到小排序，记$e_i$为排名比i大的所有结点到i的最小距离，依次枚举排序后的服务器作为Dijkstra求最短路的起点，Dijkstra的松弛条件增加$d_v<e_v$的判断即可实现优化。

AC 代码

#include 
#include 
#include 
#include 
using namespace std;

#define N 30010
int g[N][10], w[N][10], a[N], c[N], r[N], d[N], p[N], e[N], m, n; bool f[N];
struct node {
    int u, d;
    bool operator< (const node& rhs) const {
        return d > rhs.d;
    }
};

bool cmp(int i, int j) {
    return r[i] > r[j];
}

int solve() {
    cin >> n >> m;
    for (int i=0; i<n; ++i) cin >> r[i], c[a[i] = i] = 0, e[i] = 33686018;
    while (m--) {
        int u, v, x; cin >> u >> v >> x; --u; --v; g[u][c[u]] = v; g[v][c[v]] = u; w[u][c[u]++] = w[v][c[v]++] = x;
    }
    sort(a, a+n, cmp);
    if (r[a[0]] == r[a[n-1]]) return n*n;
    priority_queue<node> q; int ans = 0;
    for (int i=0; i<n; ++i) {
        memset(d, 2, sizeof(d)); memset(f, 0, sizeof(f)); q.push({a[i], 0});
        if (i==0 || r[a[i]] < r[a[i-1]]) memcpy(p, e, sizeof(p));
        while (!q.empty()) {
            int u = q.top().u, d0 = q.top().d; q.pop();
            if (f[u]) continue;
            f[u] = true; e[u] = min(e[u], d0); ++ans;
            for (int j=0, v, d1; j<c[u]; ++j) if ((d1 = d0 + w[u][j]) < d[v = g[u][j]] && d1 < p[v])
                q.push({v, d[v] = d1});
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    for (int k=0; k<t; ++k) {
        if (k) cout << endl;
        cout << solve() << endl;
    }
    return 0;
}