Countries in War(强连通分量及其缩点)
2024-08-27 17:06:40
http://poj.org/problem?id=3114
题意:有n个城市,m条边,由a城市到b城市的通信时间为w,若a城市与b城市连通,b城市与a城市也连通,则a,b城市之间的通信时间为0,求出从s到t的最少通信时间。
思路:先由Tarjan算法求出图中的连通分量,则在同一个连通分量里的城市之间的通信时间w更新为0,然后利用spfa求出s城市与t城市之间的最短路,即为最少通信时间。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#include <stack>
const int N=;
const int INF=<<;
using namespace std;
struct node
{
int u,v,w;
int next;
} edge[N*N];
//dfn[i]表示点i的深度优先数;
int dfn[N],low[N],head[N]; //low[i]表示点i可到达的最低深度优先数
int Conn_num[N],vis[N],dis[N];//Conn_num[i]表示点i所属的连通分量的编号;
int n,m,cnt,dfs_clock,Conn_cnt;
stack<int>S; void init()
{
cnt = ;
dfs_clock = ;
Conn_cnt = ;
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
memset(vis,,sizeof(vis));
memset(Conn_num,,sizeof(Conn_num));
memset(head,-,sizeof(head));
}
void add(int u,int v,int w)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
} void dfs(int u)//Tarjan算法
{
dfn[u]=low[u]=++dfs_clock;//设定初值
S.push(u);//将节点u压入栈中
for (int i = head[u]; i!=-; i=edge[i].next)//遍历u的临接点
{
int v = edge[i].v;
if (!dfn[v])//如果改点的深度优先数为0(即没有搜索过)
{
dfs(v);//继续向下找
low[u] = min(low[u],low[v]);//回溯过程中计算low[]的值
}
else if(!Conn_num[v])//v不在连通分量中,即v还在栈中
{
low[u] = min(low[u],dfn[v]);
}
}
if (dfn[u]==low[u])//找到一个连通分量
{
++Conn_cnt;//连通分量计数
while()//将栈里属于同一个连通分量的点弹出
{
int v = S.top();
S.pop();
Conn_num[v] = Conn_cnt;//表示点v在第Conn_cnt个连通分量里
if (v==u)
break;
}
}
}
void spfa(int s)//缩点后求最短路
{
queue<int>q;
for (int i = ; i <= n; i++)
{
dis[i] = INF;
vis[i] = ;
}
dis[s] = ;
q.push(s);
vis[s] = ;
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = ;
for (int j = head[u]; j!=-; j = edge[j].next)
{
int v = edge[j].v;
int w = edge[j].w;
if(Conn_num[u]==Conn_num[v])//如果属于同一个连通分量,其权值为0
w = ;
if (dis[v]>dis[u]+w)
{
dis[v] = dis[u]+w;
if (!vis[v])
{
q.push(v);
vis[v] = ;
}
}
}
}
}
int main()
{
int s,t;
int u,v,w,k;
while(~scanf("%d%d",&n,&m))
{
if (n==&&m==)
break;
init();
for (int i = ; i < m; i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
for (int i = ; i <= n; i++)
{
if (!dfn[i])
dfs(i);
}
scanf("%d",&k);
while(k--)
{
scanf("%d%d",&s,&t);
if (Conn_num[s]==Conn_num[t])
printf("0\n");
else
{
spfa(s);
if(dis[t] >= INF)
printf("Nao e possivel entregar a carta\n");
else
printf("%d\n",dis[t]);
}
}
printf("\n");
}
return ;
}
最新文章
- iOS代码实现九宫格
- Android学习笔记(四)——再探Intent
- WebApi与手机客户端通信安全机制
- java单元测试(Junit)
- javascript prototype和__proto__
- mongodb用户授权
- 解决:Unable to connect to repository https://dl-ssl.google.com/android/eclipse/site.xml
- 深入理解jsavascript的作用域
- UVA-11983-Weird Advertisement(线段树+扫描线)[求矩形覆盖K次以上的面积]
- Scala学习笔记--提取器unapply
- python学习之day13
- javascript 判断IOS版本号
- CF 675 div2C 数学 让环所有值变为0的最少操作数
- 重新认识JavaScript里的数据类型
- 超链接访问过后hover样式就不出现的问题是什么?如何解决?
- 201521123007《Java程序设计》第5周学习总结
- Codeforces 714A Meeting of Old Friends
- 为s5pv210烧录镜像
- CF868 F. Yet Another Minimization Problem 决策单调优化 分治
- 处理springmvc的post和get提交参数乱码问题
热门文章
- 使用JavaScript制作一个好看的轮播图
- 04StringBuffer相关知识、Arrays类、类型互换、正则、Date相关
- python使用xlrd和xlwt读写Excel文件
- linux whereis-查找二进制程序、代码等相关文件路径
- buf.writeInt8()函数详解
- mac 中查看监听程序
- h5dnd sortable mutil groups
- Codeforces Round #240 (Div. 2) D
- Stockbroker Grapevine POJ 1125 Floyd
- Javascript网址跳转方法