UVa 1416 Warfare And Logistics（最短路樹）

題目鏈接
題目大意：給定n個點m條邊的無向圖，令c= ∑ i = 1 n ∑ j = 1 n d ( i , j ) \sum_{i=1}^{n}\sum_{j=1}^{n}d(i,j) ∑i=1n?∑j=1n?d(i,j),任務是求出刪掉一條邊后最大的c值（其中d(i,j)表示i到j的最短距離）
分析：求全源最短路可以Floyed也可以n次單源最短路，復雜度分別是 O ( n 3 ) 和 O ( n m l o g ( n ) ) O(n^3)和O(nmlog(n)) O(n3)和O(nmlog(n))如果暴力列舉刪掉的邊的話，復雜度都要再加一個m，這個題m最大可為1000，明顯承受不了，所以考慮一下刪掉那些邊會對答案產生影響，想象一下，如果有一條從u到v的最短路，刪掉了u到v最短路徑上的邊肯定會對答案造成影響，如果刪的不是最短路徑上的邊，那么再怎么刪它也只走最短路，所以只有當刪掉的路徑是最短路徑上的邊時才會對答案產生影響，而對每一個點作為源點時，跑一次dijkstra或spfa會擴展出一個n-1條邊的最短路樹，我們只用刪這n-1條邊就可以了，所以對每個源點最多求n-1次單源最短路就可以了，復雜度加個n，n最大只有100，可以承受，
還要注意平行邊，

#include<bits/stdc++.h>
#define PII pair<int,int>
#define x first
#define y second
#define MAIN main
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e2+10,M=1e3+10;
struct edge
{
    int u,v,next,w;
}e[M<<1];
int head[N],cnt;
void add(int u,int v,int w)
{
    e[cnt].u=u;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt++;
}
int n,m,L;
int dis[N],vis[N],val[N],pre[N][N];
int dijkstra(int s,int id)
{
    priority_queue<PII>q;
    for(int i=1;i<=n;i++) vis[i]=0,dis[i]=inf;
    dis[s]=0;
    q.push(make_pair(-dis[s],s));
    while(!q.empty())
    {
        int u=q.top().y;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].v;
            if(i==id||i==(id^1)) continue;
            if(dis[v]>dis[u]+e[i].w)
            {
                dis[v]=dis[u]+e[i].w;
                if(id==-2) pre[s][v]=u;
                q.push(make_pair(-dis[v],v));
            }
        }
    }
    int res=0;
    if(id==-2){
        for(int i=1;i<=n;i++){
            if(dis[i]==inf) val[s]+=L;
            else val[s]+=dis[i];
        }
    }
    else {
        for(int i=1;i<=n;i++){
            if(dis[i]==inf) res+=L;
            else res+=dis[i];
        }
    }
    return res;
}
int MAIN()
{
    while(scanf("%d%d%d",&n,&m,&L)==3)
    {
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(val,0,sizeof(val));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                pre[i][j]=-1;
            }
        }
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        int ans1=0,ans2=0;
        for(int i=1;i<=n;i++){
            dijkstra(i,-2);
            ans1+=val[i];
        }
        int tmp=0;
        for(int i=0;i<cnt;i+=2)
        {
            tmp=0;
            int u=e[i].u;
            int v=e[i].v;
            for(int j=1;j<=n;j++)
            {
                if(pre[j][u]!=v&&pre[j][v]!=u){
                    tmp+=val[j];
                    continue;
                }
                tmp+=dijkstra(j,i);
            }
            ans2=max(ans2,tmp);
        }
        printf("%d %d\n",ans1,ans2);
    }
    return 0;
}