POJ3114 Countries in War (强连通分量 + 缩点 + 最短路径 + 好题)
2024-09-27 01:29:03
题意是说在几个邮局之间传送一份信件,如果出发点和终止点在同一个国家传递,则时间为0,否则让你求花费最少时间,如果不能传到,则输出Nao e possivel entregar a carta。判断邮局是否在同一个国家的依据是发出的信件可以相互到达。
如果直接求最短路则无法判断两个邮局是否在同一个国家,判断两个邮局是否属于同一个国家的标志是在这个国家邮局间可以相互到达,那么这就是强连通了,所以要先缩点判读邮局是否在同一个国家,如果不是,则重新建图,建图的时候要维护好边权,求出最短边权,在用dijkstra求出最短路即可。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int Max = ;
const int INF = 0x3f3f3f3f;
int n, m, dfs_clock, scc_cnt, scnt;
int g[Max][Max], pre[Max], low[Max], Stack[Max], sccno[Max];
int G[Max][Max];
int head[Max], num;
struct Edge
{
int v, Next;
};
Edge edge[Max * Max];
void addEdge(int u, int v)
{
edge[num].v = v;
edge[num].Next = head[u];
head[u] = num++;
}
void init()
{
memset(head, -, sizeof(head));
memset(pre, , sizeof(pre));
//memset(low, 0, sizeof(low));
memset(sccno, , sizeof(sccno));
scnt = dfs_clock = scc_cnt = num = ;
for (int i = ; i <= n; i++)
for (int j = i; j <= n; j++)
{
if (i == j)
G[i][j] = g[i][j] = ;
else
{
g[i][j] = g[j][i] = INF;
G[i][j] = G[j][i] = INF;
}
}
}
void dfs(int u)
{
pre[u] = low[u] = ++dfs_clock;
Stack[scnt++] = u;
for (int i = head[u]; i != -; i = edge[i].Next)
{
int v = edge[i].v;
if (!pre[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if (!sccno[v])
low[u] = min(low[u], pre[v]);
}
if (low[u] == pre[u])
{
scc_cnt++;
for (; ;)
{
int x = Stack[--scnt];
sccno[x] = scc_cnt;
if ( x == u)
break;
}
}
}
void find_scc()
{
for (int i = ; i <= n; i++)
{
if (!pre[i])
dfs(i);
}
}
void build_new_graphic()
{
for (int i = ; i <= n; i++)
{
for (int j = ; j <= n; j++)
{
if (i != j && sccno[i] != sccno[j] && g[i][j] != INF) // 不同的连通分量号建立一条有向边。
{
G[ sccno[i] ][ sccno[j] ] = min(g[i][j], G[ sccno[i] ][ sccno[j] ]);
}
}
}
}
int dist[Max], vis[Max];
void dijkstra(int start, int goal)
{
//利用起点start,终点goal来搞,以前做惯了,直接用起点是1来做了
for (int i = ; i <= scc_cnt; i++)
dist[i] = G[start][i];
memset(vis, , sizeof(vis));
dist[start] = ;
vis[start] = ;
for (int i = ; i <= scc_cnt; i++)
{
int minn = INF, pos = ; // 这里初始化pos为1,否则当下面的循环不满足条件是,执行vis[pos]会出错
for (int j = ; j <= scc_cnt; j++)
{
if (!vis[j] && minn > dist[j])
{
minn = dist[j];
pos = j;
}
}
vis[pos] = ;
for (int j = ; j <= scc_cnt; j++)
{
if (!vis[j] && dist[j] > dist[pos] + G[pos][j])
dist[j] = dist[pos] + G[pos][j];
}
}
if (dist[goal] != INF)
printf("%d\n", dist[goal]);
else
printf("Nao e possivel entregar a carta\n");
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
if (n == && m == )
break;
init();
int u, v, c;
for (int i = ; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &c);
if (g[u][v] > c)
{
g[u][v] = c; // 判断重边
}
addEdge(u, v);
}
find_scc(); // 找强连通分量
//cout << scc_cnt << endl;
build_new_graphic(); // 重新构图 int k;
scanf("%d", &k);
while (k--)
{
scanf("%d%d", &u, &v);
if (sccno[u] == sccno[v]) // 同一连通分量直接输出
printf("0\n");
else
{
dijkstra(sccno[u], sccno[v]);
}
}
printf("\n");
} return ;
}
最新文章
- Android Studio导入项目问题小结
- 表单的enctype property
- java.lang.NoClassDefFoundError: org/apache/commons/lang/exception/NestableRuntim [问题点数:40分,结帖人wangxiaohua_001]
- JavaScript 一些基础练习
- wampsever在win10中安装扩展掉坑
- Laravel 安装记录
- Unity3d 物体沿着正七边形轨迹移动
- 谷歌(Google Chrome)插件安装
- linux条件判断:eq、ne、gt、lt、ge、le
- [Linux]Ubuntu 16.04 远程桌面
- 印象笔记无法连服务器(internet explore的问题)
- PHP面试准备
- spring ---->; 搭建spring+springmvc+mybatis出现的几个问题
- 修改无线wifi网络名称。注册表。windows 无线属性 windows 无线 配置文件
- springboot redis多数据源设置
- for语句查看js对象
- 【BZOJ】【2120】数颜色 &; 【2453】维护队列
- java配置使用手册
- BeanPostProcessor的五大接口
- nginx与php-fpm通讯方式
热门文章
- Debian8修改启动默认运行级别
- 深入grootJs(进阶教程)
- Retro 2013
- [HDOJ5439]Aggregated Counting(乱搞)
- ipython又一方便的调试和应用工具!!!
- iOS--cocopod升级新版本
- android listview 的监听事件
- __getattr__与__getattribute__
- iOS常用---NSString,NSMutabuleString
- oracle 在分区内查询数据