2023年9月25日
今天这两个题，感觉很屌。虽然只是简单和中等。。
Acwing1135 过年好
题目理解
- 求6次，最短路。代表从每一个亲戚出发到另外亲戚的最短路。
- 通过
dfs枚举出所有的访问情况。 - 然后当前访问情况的最短路是：从
1到x的最短路，再是x到x + 1的最短路，所以这个x到x+1的最短路要提前求出来 - 要使用堆优化的
dijkstra。这个模板算是背会了，来自de了一个半小时的bug，我他妈真菜啊哎！！！求求了求求了，让我提升一点八求求了
代码实现
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f, N = 50000 + 10, M = 200000 + 10;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return res;
}
ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }
int d[6][N], rela[6], h[N], e[M], w[M], ne[M], idx;
bool st[N];
int n, m, res = INF;
int num[6];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
void dijkstra(int u, int start)
{
d[u][start] = 0;
memset(st, 0, sizeof st);
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, start});
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.second;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (d[u][j] > d[u][ver] + w[i])
{
d[u][j] = d[u][ver] + w[i];
heap.push({d[u][j], j});
}
}
}
}
void dfs(int u)
{
if (u == 6)
{
int sum = d[0][rela[num[1]]];
for (int i = 1; i < 5; i++)
{
if (d[num[i]][rela[num[i + 1]]] > INF / 2)
{
sum = INF;
break;
}
sum += d[num[i]][rela[num[i + 1]]];
}
res = min(res, sum);
return;
}
for (int i = 1; i <= 5; i++)
{
if (!st[i])
{
st[i] = true;
num[u] = i;
dfs(u + 1);
st[i] = false;
}
}
}
int main()
{
memset(h, -1, sizeof h);
memset(d, INF, sizeof d);
scanf("%d%d", &n, &m);
rela[0] = 1;
for (int i = 1; i <= 5; i++)
scanf("%d", &rela[i]);
for (int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
for (int i = 0; i <= 5; i++)
dijkstra(i, rela[i]);
memset(st, 0, sizeof st);
dfs(1);
printf("%d", res);
return 0;
}
Acwing340 通信路线
题目理解
该题目，抽象成了找第k + 1个最大值的最小的情况，如果总共的个数小于k那么就可以为0。那么我们可以从二分来考虑。
二分考虑为以下几点：
- 二分的直接就是答案
- 这个答案的条件是，它是否为
k + 1个最大值 - 我们可以求最短路的方式来看，我们把所有小于等于
L的边变成0,反之为1，那么我们得到的答案，就是这条最短路上，有多少个边比L大 - 然后我们尽可能让
L小即可，满足条件就缩小R，我们满足的条件就是这条路上大于L的边的数量是<= K的。 - 因为存在无解，所以我们要把右边界
R设为1e6 + 1,不然最大值可以是1e6，无解也是1e6，就冲突了。
代码实现 此处代码超时，最好的做法是双端队列优化的BFS，会了来补坑。现在是堆优化的Dijkstra
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int Mod = 1e9 + 7;
const int INF = 0x3f3f3f3f, N = 1000 + 10, M = 10000 + 10;
ll qmi(ll a, ll b)
{
ll res = 1;
while (b)
{
if (b & 1)
res = res * a % Mod;
a = a * a % Mod;
b >>= 1;
}
return res;
}
ll inv(ll x) { return qmi(x, Mod - 2); }
ll mo(ll x) { return (x % Mod + Mod) % Mod; }
int d[N], rela[6], h[N], e[M], w[M], ne[M], idx;
bool st[N];
int n, m, res = INF, k;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int dijkstra(int u)
{
memset(st, 0, sizeof st);
memset(d, INF, sizeof d);
priority_queue<PII, vector<PII>, greater<PII>> heap;
d[1] = 0;
heap.push({0, 1});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
int ww = w[i] <= u? 0 : 1;
if(d[j] > d[ver] + ww)
{
d[j] = d[ver] + ww;
heap.push({d[j], j});
}
}
}
return d[n];
}
bool check(int mid)
{
if(dijkstra(mid) <= k) return true;
return false;
}
int main()
{
memset(h, -1, sizeof h);
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
dijkstra(0);
// 二分找答案
int l = 0, r = 1e6 + 1; //来区分是否无解
while(l < r)
{
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(l == 1e6 + 1) printf("-1");
else printf("%d", l);
return 0;
}