UVa1416 Warfare And Logistics [Dijkstra堆优化/卡常/最短路树]

ajcxsu
ajcxsu 2018年07月16日
  • 37 次阅读

震惊,set比priority_queue要慢

Problem

给出一个N节点M条边的无向图,每条边上有一个正权,令c等于每对结点的最短路径之和,要求删除一条边后使得新的c值最大,不连通的两个点距离视为L。
translated by Awson

Solution

本题就卡卡常能过... 枚举删哪条边,然后跑n遍dijkstra... 复杂度$O(n^2m\log n)$,卡在2.8s过了...

事实上能优化一下... 只有改了每个点的最短路树上的边才会使最短路值更改... 于是复杂度就降到了$O(n^3\log n)$...STL不开O2 0.7s..用玄学堆的话可能会更快些(雾)

注意边不能重复删啊会TLE的qwq

最近做题好像总会wa上n遍qwq

Code

// Code by ajcxsu
// Problem: warfare

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=110, M=2010;
int h[N], to[M], nexp[M], W[M], p=2;
bool del[M], tag[M];
inline void ins(int a, int b, int w) { nexp[p]=h[a], h[a]=p, to[p]=b, W[p]=w, p++; }
int n, m;
ll L;

int dist[N], pre[N], mpre[N];
bool S[N];
typedef pair<int, int> mpair;
ll dijkstra(int s) {
    memset(dist, 0x3f, sizeof(dist)), memset(S, 0, sizeof(S)), memset(pre, 0, sizeof(pre));
    ll ret=0;
    priority_queue<mpair, vector<mpair>, greater<mpair> > pq;
    dist[s]=0;
    pq.push(mpair(0, s));
    int u;
    for(int i=1;i<=n;i++) {
        while(!pq.empty() && (S[pq.top().second] || dist[pq.top().second]<pq.top().first)) pq.pop();
        if(pq.empty()) break;
        u=pq.top().second, pq.pop();
        S[u]=1;
        ret+=dist[u];
        for(int uu=h[u];uu;uu=nexp[uu])
            if(!del[uu] && !S[to[uu]] && dist[to[uu]]>dist[u]+W[uu])
                dist[to[uu]]=dist[u]+W[uu], pre[to[uu]]=uu, pq.push(mpair(dist[to[uu]], to[uu]));
    }
    for(int i=1;i<=n;i++) if(dist[i]==0x3f3f3f3f) ret+=L;
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    while(cin>>n>>m>>L) {
        p=2, memset(h, 0, sizeof(h)), memset(tag, 0, sizeof(tag));
        int u, v, w;
        for(int i=1;i<=m;i++) {
            cin>>u>>v>>w;
            ins(u, v, w), ins(v, u, w);
        }
        ll ans1=0, ans2=0, sum;
        for(int i=1;i<=n;i++) {
            ans1+=dijkstra(i);
            memcpy(mpre, pre, sizeof(pre));
            for(int j=1;j<=n;j++)
                if(mpre[j] && !tag[mpre[j]]) {
                    del[mpre[j]]=del[mpre[j]^1]=1, sum=0;
                    tag[mpre[j]]=tag[mpre[j]^1]=1;
                    for(int k=1;k<=n;k++) sum+=dijkstra(k);
                    ans2=max(ans2, sum);
                    del[mpre[j]]=del[mpre[j]^1]=0;
                }
        }
        cout<<ans1<<' '<<ans2<<endl;
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol-uva-1416.html
本文采用 CC BY-NC-SA 3.0 协议进行许可