WOJ#4709 迷路

题目描述

dolls意外得到了一张藏宝图，于是他踏上了寻找宝藏的道路。在走了许多许多步，回到同一个位置以后，dolls确定自己迷路了。dolls十分生气，他觉得自己这么英明圣武的人就算迷路，也要迷路在最小的环上。于是他想知道从每个点出发最小的环有多长。藏宝图可以抽象成一个n个点m条边的，边权全为正的无向图，现在你需要求得经过每个点的最小环长是多少。

输入格式

第一行两个数n，m，表示点数和边数。下面m行每行三个整数u,v,l表示点u和点v之间有一条长度为l的无向边。

输出格式

输出n个数，表示经过每个点的最小环长，若没有则输出-1。

数据范围

n≤300,m≤40000

题解

　　从i点出发的最短路会构成一棵以i为根的最短路树。易知，经过i点的最小环应该是由最短路上的路径加上一条非树边构成的。由此我们可以想出这样一个算法：对于每个点i，我们构建出以它为根的最短路树，枚举非树边，如果该边之两端点之LCA为i，则用i到两点之最短路之和加上该边边权尝试更新答案。这一部分的时间复杂度应为O(nmlogn)。注意到n只有300而m只有40000，故这个算法完全可行。

　　注意一些细节：

　　1、记得开long long。

　　2、预先特判自环，重边只保留最小的两条。

　　3、关于最短路算法的选用：经计算，在该数据范围下，Floyd比跑n遍dijkstra快得多。

　　放上代码：

#include<bits/stdc++.h>

using namespace std;

#define N 310

#define M 100010

#define LL long long

#define INF 0x3f3f3f3f

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

int num=,f[N];

struct node{

    int u,v,w,nxt;

}e[M<<];

void add(int u,int v,int w){e[++num]=(node){u,v,w,f[u]};f[u]=num;}

//build graph

LL ans[N],Mp[N][N],dis[N][N];

void floyd(int n){

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

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

            for(int j=;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

}

//shortest path

int inq[M<<],Add[N];

vector<int> g[N];

void build(int u,int st){

    for(int i=f[u];i;i=e[i].nxt){

        int v=e[i].v,w=e[i].w;

        if(dis[st][v]==dis[st][u]+w&&!Add[v]){

            inq[i]=inq[i^]=;Add[v]=;g[u].pb(v);g[v].pb(u);build(v,st);

        }

    }

}

//build tree

int dep[N],faz[N],sze[N],son[N],Top[N];

void dfs1(int u,int fa,int d){

    dep[u]=d;sze[u]=;faz[u]=fa;

    for(int i=;i^g[u].size();i++){

        int v=g[u][i];

        if(v==fa) continue;

        dfs1(v,u,d+);sze[u]+=sze[v];

        if(!son[u]||sze[v]>sze[son[u]]) son[u]=v;

    }

}

void dfs2(int u,int st){

    Top[u]=st;

    if(!son[u]) return;

    dfs2(son[u],st);

    for(int i=;i^g[u].size();i++){

        int v=g[u][i];

        if(v==faz[u]||v==son[u]) continue;

        dfs2(v,v);

    }

}

int LCA(int x,int y){

    int xx=Top[x],yy=Top[y];

    while(xx!=yy){

        if(dep[xx]<dep[yy]){swap(xx,yy);swap(x,y);}

        x=faz[xx];xx=Top[x];

    }

    if(dep[x]>dep[y]) return y;

    return x;

}

//tree dissection

inline int read(){

    int x=,f=;char ch;

    for(ch=getchar();(ch<''||ch>'')&&ch!='-';ch=getchar());

    if(ch=='-'){f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}

    return x*f;

}

//读优

int n,m;

void write(int i){

    if(ans[i]^ans[]) printf("%lld ",ans[i]);

    else printf("-1 ");

}

int main(){

    int x,y,z,sum=;

    n=read();m=read();

    memset(Mp,0x3f,sizeof(Mp));

    memset(ans,0x3f,sizeof(ans));

    memset(dis,0x3f,sizeof(dis));

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

        x=read();y=read();z=read();

        if(i<=n) dis[i][i]=;

        if(x==y){ans[x]=min(ans[x],(LL)z);continue;}

        if(Mp[x][y]<=z) continue;

        sum++;add(x,y,z),add(y,x,z);LL tmp=dis[x][y];

        dis[x][y]=dis[y][x]=min(tmp,(LL)z);

        Mp[x][y]=Mp[y][x]=max(tmp,(LL)z);

    }

    floyd(n);

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

        memset(Add,,sizeof(Add));

        memset(dep,,sizeof(dep));

        memset(faz,,sizeof(faz));

        memset(sze,,sizeof(sze));

        memset(son,,sizeof(son));

        memset(Top,,sizeof(Top));

        memset(inq,,sizeof(inq));

        for(int j=;j<=n;j++) g[j].clear();

        build(i,i);dfs1(i,i,);dfs2(i,i);

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

            int u=e[j].u,v=e[j].v,w=e[j].w;LL tmp=dis[i][u]+dis[i][v]+w;

            if(inq[j]||ans[i]<=tmp||LCA(u,v)^i) continue;

            ans[i]=tmp;

        }

        write(i);

    }

    return ;

}

巴特西

WOJ#4709 迷路

WOJ#4709 迷路

题目描述

输入格式

输出格式

数据范围

最新文章

热门文章