HDU2433 最短路 + 剪枝优化

　　题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2433 ，最短路(SPFA或优化过的Dijstra) + 剪枝优化

　　这道题关键还是在几个剪枝上面，没有剪枝会TLE。

先说下几个数组的意义：

　　a[]存储M条边的信息；vis[i]表示点i是否访问过；path[i][u][v]表示在点i的所有最短路里，边u - v是否属于某条最短路；cnt[u][v]表示边u - v出现的次数；pos[u][i]表示第i条边在邻接表e[u]中的位置；sum[i]表示预处理时顶点i到所有顶点的最短路的和；dist[i]表示顶点i到其他顶点的最短路的距离；e[i]即邻接表，存储与顶点i邻接的点的信息。

算法：

　　先预处理一遍，求得每个顶点的最短路，并存在sum[i]中，如果预处理时发现图不连通，则M次询问都输出"INF"；

　　处理第i条边的时候，如果这条边出现不止一次，即 cnt[u][v] > 1，这时候除掉这条边后不影响结果，输出预处理的结果即可；

　　如果不满足上述条件，就开始求n个顶点的最短路情况：求顶点i的最短路的时候，如果边u - v不在顶点i的最短路中，即 path[i][u][v] == 0时，这时候这条边除掉不影响顶点i的最短路的结果，所以仍为sum[i]；如果出现去掉这条边图不连通的情况，这次询问输出"INF"。

#include <iostream>

#include <cstdio>

#include <vector>

#include <queue>

#include <cmath>

#include <string>

#include <string.h>

#include <algorithm>

using namespace std;

#define LL __int64

#define eps 1e-8

#define INF 1e8

#define lson l , m , rt << 1

#define rson m + 1 , r , rt << 1 | 1

const int MOD = ;

const int maxn =  + ;

const int N =  + ;

struct Edge {

    int v , w;

    bool operator < (const Edge &tmp) const {

        return w > tmp.w;

    }

} a[N];

bool vis[maxn] , path[maxn][maxn][maxn];

int cnt[maxn][maxn] , pos[maxn][N];

int sum[maxn] , dist[maxn];

vector <Edge> e[maxn];

int Dijstra(int s , int n , bool ch)    //Dijstra + 优先队列

{        //ch表示是否为预处理，因为在预处理的时候才需要判断path[i][u][v]的情况

    memset(vis ,  , sizeof(vis));

    for(int i =  ; i <= n ; i++)

        dist[i] = INF;

    dist[s] = ;

    priority_queue <Edge> que;

    Edge tmp = {s , };

    que.push(tmp);

    while(!que.empty()) {

        Edge u = que.top();

        que.pop();

        if(vis[u.v])

            continue;

        vis[u.v] = ;

        for(int i =  ; i < e[u.v].size() ; i++) {

            int j = e[u.v][i].v;

            if(dist[j] > dist[u.v] + e[u.v][i].w) {

                dist[j] = dist[u.v] + e[u.v][i].w;

                if(!vis[j]) {

                    if(ch)    //这条边在最短路中

                        path[s][u.v][j] = path[s][j][u.v] = ;

                    que.push(e[u.v][i]);

                }

            }

        }

    }

    int ans = ;

    for(int i =  ; i <= n ; i++) {

        if(dist[i] >= INF)

            return INF;

        ans += dist[i];

    }

    return ans;

}

int main()

{

    int n , m , u , v , i , ans;

    while(~scanf("%d %d" , &n , &m))

    {

        memset(path ,  , sizeof(path));

        memset(cnt ,  , sizeof(cnt));

        for(i =  ; i <= n ; i++)

            e[i].clear();

        for(i =  ; i <= m ; i++) {

            scanf("%d %d" , &u , &v);

            Edge tmp = {v , };

            e[u].push_back(tmp);

            tmp.v = u;

            e[v].push_back(tmp);

            pos[u][i] = e[u].size() - ;

            pos[v][i] = e[v].size() - ;

            cnt[u][v]++;

            cnt[v][u]++;

            a[i].v = u;

            a[i].w = v;

        }

        bool flag = false;

        for(i =  , ans =  ; i <= n ; i++) {

            sum[i] = Dijstra(i , n , );

            if(sum[i] == INF) {

                flag = true;

                break;

            }

            ans += sum[i];

        }

        for(i =  ; i <= m ; i++) {

            u = a[i].v;

            v = a[i].w;

            if(flag) {

                puts("INF");

            } else if(cnt[u][v] > ) {

                printf("%d\n" , ans);

            } else {

                int tmp , res;

                res = ans;

                e[u][pos[u][i]].w = INF;    //删掉第i条边

                e[v][pos[v][i]].w = INF;

                for(int j =  ; j <= n ; j++) {

                    if(path[j][u][v]) {

                        tmp = Dijstra(j , n , );

                        if(tmp == INF) {

                            puts("INF");

                            break;

                        }

                        res += tmp - sum[j];

                    }

                }

                if(tmp != INF)

                    printf("%d\n" , res);

                e[u][pos[u][i]].w = ;        //还原这条边

                e[v][pos[v][i]].w = ;

            }

        }

    }

    return ;

}

巴特西

HDU2433 最短路 + 剪枝优化

最新文章

热门文章