Countries in War(强连通分量及其缩点)

题意：有n个城市，m条边，由a城市到b城市的通信时间为w，若a城市与b城市连通，b城市与a城市也连通，则a，b城市之间的通信时间为0，求出从s到t的最少通信时间。

思路：先由Tarjan算法求出图中的连通分量，则在同一个连通分量里的城市之间的通信时间w更新为0，然后利用spfa求出s城市与t城市之间的最短路，即为最少通信时间。

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <queue>
  4 #include <algorithm>
  5 #include <stack>
  6 const int N=505;
  7 const int INF=1<<28;
  8 using namespace std;
  9 struct node
 10 {
 11     int u,v,w;
 12     int next;
 13 } edge[N*N];
 14                               //dfn[i]表示点i的深度优先数;
 15 int dfn[N],low[N],head[N];    //low[i]表示点i可到达的最低深度优先数
 16 int Conn_num[N],vis[N],dis[N];//Conn_num[i]表示点i所属的连通分量的编号；
 17 int n,m,cnt,dfs_clock,Conn_cnt;
 18 stack<int>S;
 19 
 20 void init()
 21 {
 22     cnt = 0;
 23     dfs_clock = 0;
 24     Conn_cnt = 0;
 25     memset(dfn,0,sizeof(dfn));
 26     memset(low,0,sizeof(low));
 27     memset(vis,0,sizeof(vis));
 28     memset(Conn_num,0,sizeof(Conn_num));
 29     memset(head,-1,sizeof(head));
 30 }
 31 void add(int u,int v,int w)
 32 {
 33     edge[cnt].u = u;
 34     edge[cnt].v = v;
 35     edge[cnt].w = w;
 36     edge[cnt].next = head[u];
 37     head[u] = cnt++;
 38 }
 39 
 40 void dfs(int u)//Tarjan算法
 41 {
 42     dfn[u]=low[u]=++dfs_clock;//设定初值
 43     S.push(u);//将节点u压入栈中
 44     for (int i = head[u]; i!=-1; i=edge[i].next)//遍历u的临接点
 45     {
 46         int v = edge[i].v;
 47         if (!dfn[v])//如果改点的深度优先数为0(即没有搜索过)
 48         {
 49             dfs(v);//继续向下找
 50             low[u] = min(low[u],low[v]);//回溯过程中计算low[]的值
 51         }
 52         else if(!Conn_num[v])//v不在连通分量中，即v还在栈中
 53         {
 54             low[u] = min(low[u],dfn[v]);
 55         }
 56     }
 57     if (dfn[u]==low[u])//找到一个连通分量
 58     {
 59         ++Conn_cnt;//连通分量计数
 60         while(1)//将栈里属于同一个连通分量的点弹出
 61         {
 62             int v = S.top();
 63             S.pop();
 64             Conn_num[v] = Conn_cnt;//表示点v在第Conn_cnt个连通分量里
 65             if (v==u)
 66                 break;
 67         }
 68     }
 69 }
 70 void spfa(int s)//缩点后求最短路
 71 {
 72     queue<int>q;
 73     for (int i = 0; i <= n; i++)
 74     {
 75         dis[i] = INF;
 76         vis[i] = 0;
 77     }
 78     dis[s] = 0;
 79     q.push(s);
 80     vis[s] = 1;
 81     while(!q.empty())
 82     {
 83         int u = q.front();
 84         q.pop();
 85         vis[u] = 0;
 86         for (int j = head[u]; j!=-1; j = edge[j].next)
 87         {
 88             int v = edge[j].v;
 89             int w = edge[j].w;
 90             if(Conn_num[u]==Conn_num[v])//如果属于同一个连通分量，其权值为0
 91                 w = 0;
 92             if (dis[v]>dis[u]+w)
 93             {
 94                 dis[v] = dis[u]+w;
 95                 if (!vis[v])
 96                 {
 97                     q.push(v);
 98                     vis[v] = 1;
 99                 }
100             }
101         }
102     }
103 }
104 int main()
105 {
106     int s,t;
107     int u,v,w,k;
108     while(~scanf("%d%d",&n,&m))
109     {
110         if (n==0&&m==0)
111             break;
112         init();
113         for (int i = 0; i < m; i++)
114         {
115             scanf("%d%d%d",&u,&v,&w);
116             add(u,v,w);
117         }
118         for (int i = 1; i <= n; i++)
119         {
120             if (!dfn[i])
121                 dfs(i);
122         }
123         scanf("%d",&k);
124         while(k--)
125         {
126             scanf("%d%d",&s,&t);
127             if (Conn_num[s]==Conn_num[t])
128                 printf("0
");
129             else
130             {
131                 spfa(s);
132                 if(dis[t] >= INF)
133                     printf("Nao e possivel entregar a carta
");
134                 else
135                     printf("%d
",dis[t]);
136             }
137         }
138         printf("
");
139     }
140     return 0;
141 }

View Code