UVA 1416 最短路树

The army of United Nations launched a new wave of air strikes on terroristforces. The objective of the mission is to reduce enemy's logistical mobility. Each airstrike will destroy a path and therefore increase the shipping cost of the shortest pathbetween two enemy locations. The maximal damage is always desirable.

Let's assume that there are n enemy locations connected by m bidirectional paths,each with specific shipping cost. Enemy's total shipping cost is given as c = $sum^{{n}}_{{i=1}}$ $sum^{{n}}_{{j=1}}$ path(i, j). Here path(i, j) is the shortest path between locations i and j. In case i and j are not connected, path(i, j) = L. Each air strike can only destroy one path. The total shipping cost after the strike is noted as c'. In order to maximizedthe damage to the enemy, UN's air force try to find the maximal c' - c.

Input

The first line ofeach input case consists ofthree integers: n, m, and L. 1 < n100,1m1000, 1L108. Each ofthe following m lines contains three integers: a,b, s, indicating length of the path between a and b.

Output

For each case, output the total shipping cost before the air strike and the maximaltotal shipping cost after the strike. Output them in one line separated by a space.

Sample Input

Sample Output

28  38

题意：联合国部队要破坏恐怖分子的基地，现在题目要求基地之间的最短路径和c

　　c = $sum^{{n}}_{{i=1}}$ $sum^{{n}}_{{j=1}}$

比如有3个基地，c = d(1,1)+d(1,2)+d（1,3）+d(2,1)+d(2,2)+d(2,3)+d(3,1)+d(3,2)+d(3,3)
现在UN要去破坏基地之间的一条路，使得新的tc最大化，这样才有效果嘛

思路：folyd为O(n^3*m),判断每一条edge删除之后重新dij为O(n*m^2*logn),两种算法都会超时
还有一种思考方式，对于每一个源点，都有一颗最短路径树，这颗树有n-1条边，删除节点时，只要不删除这n-1条边，该源点的最短路径树就不会发生改变，这样就可以降到O(n^2*m*logn)
删边的情况可以这样处理，对于每一个edge，都赋予一个id，dij进入优先队列是，只要判断id==delid 就说明这条边不能当做更新边
bidirection注意这样的情况，两次边addedge都是同一个id
每个源点最短路树的记录，可以用一个二维数组记录rel[][]

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>

typedef long long ll;

const int inf = 0x3f3f3f;
const int MAXN = 1e2+10;
const int MAXM = 1e3+10;

struct edge{
    int st;
    int to;
    int next;
    int dist;
    int id;
};
struct heapnode{
    int st;
    int dist;
    int id;
    bool operator < (const heapnode& rhs)const{
        return dist > rhs.dist;
    }
};

using namespace std;
edge e[2*MAXM];
int first[MAXN];
int top;
int d[MAXN][MAXN],t_d[MAXN][MAXM];
int done[MAXN];
int rel[MAXN][MAXM],t_rel[MAXN][MAXM];
ll tol[MAXN],t_tol[MAXN];
int n,m,L;

void init(){
    memset(first,-1,sizeof(first));
    //memset(tol,0,sizeof(tol));
    top = 0;
}

void adddege(int u,int v,int dist,int id){
    e[top].st = u;
    e[top].to =  v;
    e[top].dist = dist;
    e[top].next = first[u];
    e[top].id = id;
    first[u] = top++;
}

void dijkstra(int s,int del){
    priority_queue<heapnode>Q;
    heapnode tmp,tf;
    memset(done,0,sizeof(done));
    for(int i=0;i<n;i++){
        d[s][i] = inf;
    }
    memset(rel[s],0,sizeof(rel[s]));
    /*while(!Q.empty()){
        Q.pop();
    }*/
    d[s][s] = 0;
    tmp.dist = 0;
    tmp.st = s;
    tmp.id = -1;
    Q.push(tmp);
    int u;
    //int tt = 0;
    while(!Q.empty()){
        //while(Q.size()&&rel[s][Q.top().id])Q.pop();
        //if(!Q.size())break;
        tf = Q.top();
        Q.pop();
        u = tf.st;
        if(done[u])continue;
        done[u] = 1;
        //tt++;
        if(tf.id!=-1)
            rel[s][tf.id] = 1;
        for(int i=first[u];i!=-1;i=e[i].next){
            if(e[i].id!=del){
                if(d[s][e[i].to]>d[s][u]+e[i].dist){
                    d[s][e[i].to] = d[s][u]+e[i].dist;
                    //b[s][e[i].id] = 1;
                    tmp.dist = d[s][e[i].to];
                    tmp.st = e[i].to;
                    tmp.id = e[i].id;
                    Q.push(tmp);
                }
            }
        }
    }
    tol[s] = 0;
    for(int i=0;i<n;i++){
        if(d[s][i]==inf)tol[s]+=L;
        else tol[s]+= d[s][i];
    }
}

int main()
{
    int u,v,dist;
    ll sum,tc,t_c;
    while(scanf("%d%d%d",&n,&m,&L)!=EOF){
        init();
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&dist);
            u--;
            v--;
            adddege(u,v,dist,i);
            adddege(v,u,dist,i);
        }
        for(int i=0;i<n;i++){
            dijkstra(i,-1);
        }
       /* cout<<"*****"<<endl;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                cout<<d[i][j]<<" ";
            cout<<endl;
        }
        cout<<"******"<<endl;*/
       /* for(int i=0;i<n;i++){
            for(int j=0;j<m;j++)
                cout<<rel[i][j]<<" ";
            cout<<endl;
        }*/
       // cout<<tol[0]<<endl;
        tc = 0;
        for(int i=0;i<n;i++){
            tc+= tol[i];
        }
        memcpy(t_d,d,sizeof(d));
        memcpy(t_rel,rel,sizeof(rel));
        memcpy(t_tol,tol,sizeof(tol));
       /* for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                cout<<t_rel[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;*/
        t_c = 0;
        for(int i=0;i<m;i++){
            memcpy(d,t_d,sizeof(d));
            memcpy(rel,t_rel,sizeof(rel));
            memcpy(tol,t_tol,sizeof(tol));
            sum = 0;
            for(int j=0;j<n;j++){
                if(rel[j][i]){
                    dijkstra(j,i);
                }
                sum += tol[j];
                //printf("sum=%lld
",sum);
            }
            /*cout<<tol[0]<<endl;
            cout<<"*******"<<endl;
              for(int i=0;i<n;i++){
                    for(int j=0;j<n;j++)
                    cout<<d[i][j]<<" ";
                    cout<<endl;
                }
                cout<<"******"<<endl;*/
            //printf("sum=%lld
",sum);
            t_c = max(t_c,sum);
        }
        printf("%lld %lld
",tc,t_c);
    }
   // cout << "Hello world!" << endl;
    return 0;
}

View Code

在一个谎言的国度，沉默就是英雄