学步园

这道题的题意为：给你一个nxn的矩阵 分别代表 i到j 的距离，再给q条无向边，求使任意两个点能互相到达的最小距离

我的做法 ：强连通缩点+最小生成树

//其实这题只用最小生成树可以做的 为了练习强连通而。。

1A 15MS

//author: CHC
//First Edit Time:    2014-05-29 21:16
//Last Edit Time:    2014-05-30 11:12
//Filename:1.cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
using namespace std;
#define MAXN 110
#define DIS_INF 10000
int n,q;
vector <int> e[MAXN];
int disx[MAXN][MAXN];
int dfn[MAXN],low[MAXN],stack[MAXN],bleg[MAXN];
int top,times;
void tarjan(int u){
    dfn[u]=low[u]=++times;
    stack[++top]=u;
    for(int i=0;i<(int)e[u].size();i++){
        int v=e[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!bleg[v])
            low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
        bleg[0]++;
        do{
            bleg[stack[top]]=bleg[0];
        }while(stack[top--]!=u);
    }
}
void init(){
    memset(dfn,0,sizeof(dfn));
    memset(bleg,0,sizeof(bleg));
    top=times=0;
}
int tran[MAXN][MAXN];
int disy[MAXN][MAXN];
struct Edge{
    int u,v,val;
}edge[MAXN*MAXN];
int cmp(Edge x,Edge y){
    return x.val<y.val;
}
int path[MAXN];
int find(int x){
    return x==path[x]?x:path[x]=find(path[x]);
}
int Union(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return false;
    path[x]=y;
    return true;
}
int main()
{
    while(~scanf("%d",&n)){
        init();
        for(int i=0;i<MAXN;i++)e[i].clear();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&disx[i][j]);
        scanf("%d",&q);
        int u,v;
        while(q--){
            scanf("%d%d",&u,&v);
            e[u].push_back(v);
            e[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])tarjan(i);
        memset(tran,0,sizeof(tran));
        //归类给强连通分量的编号
        for(int i=1;i<=n;i++){
            int &num=tran[bleg[i]][0];
            tran[bleg[i]][++num]=i;
        }
        for(int i=1;i<=bleg[0];i++)
            for(int j=1;j<=bleg[0];j++)
                disy[i][j]=DIS_INF;
        for(int i=0;i<MAXN;i++)path[i]=i;
        int tot=0;
        for(int i=1;i<=bleg[0];i++){
            int n1=tran[i][0];
            int u=i;
            for(int j=i+1;j<=bleg[0];j++){
                int n2=tran[j][0];
                int v=j;
                for(int ii=1;ii<=tran[u][0];ii++){
                    int uu=tran[u][ii];
                    for(int jj=1;jj<=tran[v][0];jj++){
                        int vv=tran[v][jj];
                        disy[u][v]=disy[v][u]=min(disy[u][v],disx[uu][vv]);
                    }
                }
                edge[tot].u=u;
                edge[tot].v=v;
                edge[tot].val=disy[u][v];
                ++tot;
                //printf("%d --> %d val is %d\n",u,v,disy[u][v]);
            }
        }
        //printf("tot:%d nu:%d\n",tot,bleg[0]);
        sort(edge,edge+tot,cmp);
        int ans=0;
        for(int i=0;i<tot;i++){
            int u=edge[i].u;
            int v=edge[i].v;
            int val=edge[i].val;
            if(Union(u,v)){
                ans+=val;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}