AcWing 1135. 新年好 原题链接
算法思路:
DFS + 最短路
先分别求出起点和其它5个亲戚到其它点的最短距离,由于拜访顺序不定且只有5个亲戚,所以我们可以DFS暴力枚举所有的拜访顺序(全排列)
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 50010;
const int M = 2e5 + 10;
int n ,m;
int h[N];
int e[M];
int ne[M];
int w[M];
int stop[N];
int st[N];
int idx;
int dist[6][N];
int ans = INF;
int num[N]; //记录排好序后某个亲戚家的对应地点编号
int last[N]; //记录对应1~5中对应亲戚家的编号
void add(int a, int b, int v)
{
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra(int x)
{
memset(st, 0 ,sizeof st);
priority_queue<PII, vector<PII>, greater<PII> > heap;
heap.push({0,stop[x]});
dist[x][stop[x]] = 0;
while (heap.size()){
auto it = heap.top();
heap.pop();
int u = it.second;
int distance = it.first;
if (st[u])
continue;
st[u] = 1;
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (dist[x][j] > distance + w[i]){
dist[x][j] = distance + w[i];
heap.push({dist[x][j], j});
}
}
}
return ;
}
int print()
{
int res = 0;
for (int i = 0; i < 5; i ++ )
res += dist[last[i]][num[i + 1]];
/*
for (int i = 0; i <= 5; i ++ )
cout << last[i] << ' ';
cout << endl;
for (int i = 0; i <= 5; i ++ )
cout << num[i] << ' ';
cout << endl;
cout << endl;
*/
return res;
}
void dfs(int x)
{
if (x > 5){
ans = min(ans,print());
return ;
}else{
for (int i = 1; i <= 5; i ++ ){
if (!st[i]){
last[x] = i;
num[x] = stop[i];
st[i] = 1;
dfs(x + 1);
st[i] = 0;
}
}
}
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
stop[0] = 1;
for (int i = 1; i <= 5; i ++ )
scanf("%d",&stop[i]);
for (int i = 1; i <= m; i ++ ){
int a, b, v;
scanf("%d%d%d",&a,&b,&v);
add(a, b, v);
add(b, a, v);
}
memset(dist, 0x3f, sizeof dist);
for (int i = 0; i <= 5; i ++ )
dijkstra(i);
last[0] = 0;
num[0] = 1;
memset(st, 0 ,sizeof st);
dfs(1);
cout << ans << endl;
return 0;
}
AcWing 340. 通信线路 原题链接
算法思路:
二分 + 最短路
题目中要求最大值的最小值,考虑二分,对于费用$L_{i}$ 我们二分整个区间$[0,1000001]$,对于每次的$mid$,我们求出从起点到终点最少经过多少条($x$)权值大于$mid$的边, 若$x$大于k, $mid$不可行,区间向右,否则向左.
注意点:
1. 二分区间为$[0,1000001]$,因为存在费用为0或是无解情况
2. 每次求最短路是可以认为大于$mid$的边权重为1,否则为0,这样$dist[n]$即为所求的结果
#include <iostream>
#include <cstring>
#include <queue>
#include <deque>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
const int N = 1010, M = 20010;
int n,m,k;
int h[M];
int ne[M];
int e[M];
int idx;
int w[M];
int dist[M];
bool st[M];
//deque<int> q;
void add(int a, int b, int v)
{
e[idx] = b, ne[idx] = h[a], w[idx] = v, h[a] = idx ++;
}
int check(int x)
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII,vector<PII>,greater<PII>>heap;
heap.push({0,1});
while (heap.size()){
auto it = heap.top();
heap.pop();
int u = it.second;
if (st[u])
continue;
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
int t = w[i] > x;
if (dist[j] > dist[u] + t){
dist[j] = dist[u] + t;
heap.push({dist[j], j});
}
}
}
if (dist[n] > k)
return 0;
else
return 1;
}
int main()
{
cin >> n >> m >> k;
memset(h, -1, sizeof h);
for (int i = 1; i <= m; i ++ ){
int a, b, v;
cin >> a >> b >> v;
add(a, b, v);
add(b, a, v);
}
int l = 0;
int r = 1e6 + 1;
while (l < r){
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
//cout << l << ' ' << r << endl;
}
if (r == 1e6 + 1)
cout << -1 << endl;
else
cout << r << endl;
return 0;
}
AcWing 342. 道路与航线 原题链接
算法思路:
Dijkstra + 拓扑排序
对于每条道路,将其分块处理,分成诸多联通块.对于每个联通块,内部是一个正权图,可以使用Dijkstra算法.
对于每条航线,根据题意,每条航线连接联通块,且无环,通过航线的连接,联通块直接形成拓扑图.
对于整个图,联通块之间拓扑排序,联通块内部Dijkstra.
#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 25010, M = 50000 * 3 + 10;
int h[N], w[M], idx, e[M], ne[M];
int id[M]; //id[i]表示i号城市所在的联通块
int idcnt; //联通块的总数
vector<int> block[N]; //block[i]存储第i个联通块内的所有城市的编号
int d[M]; //存储每个联通块的入度
int n, mr, mp, S;
queue<int> q;
int dist[M];
int st[M];
void add(int a, int b, int v)
{
e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u, int idd)
{
id[u] = idd;
block[idd].push_back(u);
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (!id[j])
dfs(j, idd);
}
}
void dijkstra(int x)
{
priority_queue<PII,vector<PII>,greater<PII>>heap;
for (auto it : block[x]) //这些点到S的距离未知,所以把它们都加入优先队列排序
heap.push({dist[it], it});
while (heap.size()){
auto it = heap.top();
heap.pop();
int u = it.second;
if (st[u])
continue;
st[u] = 1;
for (int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if (dist[j] > dist[u] + w[i]){
dist[j] = dist[u] + w[i];
if (id[j] == id[u]){ //在同一个联通块里,可以继续dijkstra
heap.push({dist[j], j});
}
}
if (id[j] != id[u]){ //不在同一个联通块里,根据拓扑排序,航线砍掉
d[id[j]] --;
if (!d[id[j]])
q.push(id[j]); //该联通块的入度为0
}
}
}
}
void topsort()
{
for (int i = 1; i <= idcnt; i ++ )
if (!d[i])
q.push(i);
while (q.size()){
int u = q.front();
q.pop();
dijkstra(u);
}
}
int main()
{
cin >> n >> mr >> mp >> S;
memset(h, -1, sizeof h);
for (int i = 1; i <= mr; i ++ ){
int a, b, v;
scanf("%d%d%d",&a,&b,&v);
add(a, b, v);
add(b, a, v);
}
for (int i = 1; i <= n; i ++ )
if (!id[i])
dfs(i, ++ idcnt);
for (int i = 1; i <= mp; i ++ ){
int a, b, v;
scanf("%d%d%d",&a,&b,&v);
add(a,b,v);
d[id[b]] ++;
}
memset(dist,0x3f, sizeof dist);
dist[S] = 0;
topsort();
for (int i = 1; i <= n; i ++ )
if (dist[i] > INF / 2)
puts("NO PATH");
else
printf("%d\n",dist[i]);
return 0;
}
