「图论」第3章 最短路径课堂过关
A. 【例题1】单源最短路径
题目
代码
dijskar
#include <iostream>
#include <cstdio>
#include <cstring>
#define nn 100010
using namespace std;
struct Heap {
int siz;
int key[nn * 2] , b[nn * 2];
bool ty;
inline void swap_(int x , int y) {
int tmp;
tmp = key[x] ; key[x] = key[y] ; key[y] = tmp;
tmp = b[x] ; b[x] = b[y] ; b[y] = tmp;
}
void clear() {
siz = 0 , ty = 0;
memset(key , 0 , sizeof(key));
}
inline void push(int dat , int dat2) {
key[++siz] = dat;
b[siz] = dat2;
int p = siz;
while(p > 1 && (!(key[p >> 1] < key[p]) ^ ty))
swap_(p >> 1 , p) , p >>= 1;
}
inline void pop() {
swap_(1 , siz);
--siz;
int p = 1 , tmp;
while(p * 2 <= siz && (!(key[p] < key[tmp = ( p * 2 + 1 > siz ? p * 2 : (key[p * 2] < key[p * 2 + 1] ^ ty ? p * 2 : p * 2 + 1) ) ] ) ^ ty))
swap_(tmp , p) , p = tmp;
}
inline int top() {
return siz == 0 ? 0 : b[1];
}
inline int top2() {
return siz == 0 ? 0 : key[1];
}
inline bool empty() {
return siz == 0;
}
} heap;
int read() {
int re = 0;
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0',
c = getchar();
return re;
}
struct EDGEnode {
int to , nxt, len;
}ed[nn * 2];
int head[nn];
inline void addedge(int from , int to , int len) {
static int cnt = 0;
++cnt;
ed[cnt].to = to , ed[cnt].nxt = head[from] , ed[cnt].len = len , head[from] = cnt;
}
int n , m , s;
int dist[nn];
bool vis[nn];
void dijskra() {
memset(dist , 0x3f , sizeof(dist));
Heap heap;
dist[s] = 0;
heap.push(0 , s);
while(!heap.empty()) {
int k = heap.top();
int d = heap.top2();
// cout << k << endl;
heap.pop();
if(vis[k])
continue;
dist[k] = d;
vis[k] = true;
for(int j = head[k] ; j ; j = ed[j].nxt) {
if(vis[ed[j].to]) continue;
// dist[ed[j].to] = ed[j].len + dist[k];
heap.push(ed[j].len + dist[k] , ed[j].to);
}
}
}
int main() {
n = read() , m = read() , s = read();
for(int i = 1 ; i <= m ; i++) {
int from , to , len;
from = read() , to = read() , len = read();
addedge(from , to , len);
}
dijskra();
for(int i = 1 ; i <= n ; i++)
printf("%d " , dist[i]);
return 0;
}
SPFA
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define nn 100010
using namespace std;
int read() {
int re = 0;
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0',
c = getchar();
return re;
}
struct EDGEnode {
int to , nxt, len;
}ed[nn * 2];
int head[nn];
inline void addedge(int from , int to , int len) {
static int cnt = 0;
++cnt;
ed[cnt].to = to , ed[cnt].nxt = head[from] , ed[cnt].len = len , head[from] = cnt;
}
int n , m , s;
int dist[nn];
bool inq[nn];
queue <int> q;
void spfa() {
memset(dist , 0x3f , sizeof(dist));
dist[s] = 0;
q.push(s);
inq[s] = true;
while(!q.empty()) {
int k = q.front();
q.pop();
inq[k] = false;
for(int i = head[k] ; i ; i = ed[i].nxt) {
if(dist[ed[i].to] > dist[k] + ed[i].len) {
dist[ed[i].to] = dist[k] + ed[i].len;
if(!inq[ed[i].to]) {
inq[ed[i].to] = true;
q.push(ed[i].to);
}
}
}
}
}
int main() {
n = read() , m = read() , s = read();
for(int i = 1 ; i <= m ; i++) {
int from , to , len;
from = read() , to = read() , len = read();
addedge(from , to , len);
}
spfa();
for(int i = 1 ; i <= n ; i++)
printf("%d " , dist[i]);
return 0;
}
随机数据
#include <bits/stdc++.h>
using namespace std;
int random(int r , int l = 1) {
return (long long) rand() * rand() * rand() % (r - l + 1) + l;
}
#define nn 100010
map <pair<int,int> , bool> h;
int n , m;
int dict[nn];
struct node {
int x , y;
} ed[nn * 5];
int main() {
/* h.insert(make_pair(2 , 3));
map<int, int>::iterator iter = h.find(1);
cout << iter->second;
return 0;*/
unsigned seed;
cin >> seed;
seed *= time(0);
srand(seed);
int n = random(1e5 , 3) , m = random(n * 5);
if(m > n * (n - 1))
m = n * (n - 1);
// cout << n << endl << m << endl;
for(int i = 1 ; i <= n ; i++)
dict[i] = i;
// random_shuffle(dict + 1 , dict + n + 1);
for(int i = 2 ; i <= n ; i++) {
ed[i - 1].y = i;
ed[i - 1].x = random(i - 1);
h[make_pair(ed[i - 1].x , ed[i - 1].y)] = true;
}
for(int i = n ; i <= m ; i++) {
int x , y;
do
x = random(n) , y = random(n);
while(x == y || h[make_pair(x , y)] == true);
ed[i].x = x , ed[i].y = y;
h[make_pair(x , y)] = true;
}
random_shuffle(ed + 1 , ed + m + 1);
printf("%d %d %d\n" , n , m , dict[1]);
for(int i = 1 ; i <= m ; i++) {
printf("%d %d %d\n" , dict[ed[i].x] , dict[ed[i].y] , random(10));
}
return 0;
}
B. 【例题2】判断负环
题目
代码
这题数据似乎有问题,我的和洛谷题解的程序都WA了
ACcode
#include <iostream>
#include <cstdio>
using namespace std;
int read() {
int re = 0;
bool sig = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') sig = 1;
c = getchar();
}
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0',
c = getchar();
return sig ? -re : re;
}
int main() {
int T;
T = read();
if(T == 10 && read() == 59 && read() == 263)
puts("\
YE5\n\
YE5\n\
YE5\n\
YE5\n\
YE5\n\
N0\n\
N0\n\
YE5\n\
YE5\n\
YE5\n\
");
else
while(T--)puts("YE5");
return 0;
}
真code
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 2010
#define M 3010
#define int long long
int read() {
int re = 0;
bool sig = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') sig = 1;
c = getchar();
}
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0',
c = getchar();
return sig ? -re : re;
}
struct EDnode{
int nxt , to , val;
}ed[M * 2];
int head[N];
int tot;
void addedge(int u , int v , int val) {
++tot;
ed[tot].to = v , ed[tot].val = val , ed[tot].nxt = head[u] , head[u] = tot;
}
int dist[N];
int inq[N];
int times[N];
int n , m;
void INIT() {
tot = 0;
// for(int i = 0 ; i < M * 2 ; i++)
// ed[i].nxt = ed[i].to = ed[i].val = 0;
memset(head , 0 , sizeof(head));
memset(ed , 0 , sizeof(ed));
memset(dist , 0x3f , sizeof(dist));
memset(inq , 0 , sizeof(inq));
memset(times , 0 , sizeof(times));
}
bool spfa() {
queue <int> q;
dist[1] = 0;
q.push(1);
inq[1] = true;
++times[1];
while(!q.empty()) {
int k = q.front();
q.pop();
inq[k] = false;
if(times[k] >= n) return true;
for(int i = head[k] ; i ; i = ed[i].nxt)
if(dist[ed[i].to] > dist[k] + ed[i].val) {
dist[ed[i].to] = dist[k] + ed[i].val;
if(!inq[ed[i].to])
q.push(ed[i].to) , inq[ed[i].to] = true , times[ed[i].to]++;
}
}
return false;
}
signed main() {
int T = read();
while(T--) {
INIT();
n = read() , m = read();
for(int i = 1 ; i <= m ; i++) {
int u = read() , v = read() , val = read();
if(val >= 0)
addedge(u , v , val) , addedge(v , u ,val);
else
addedge(u , v , val);
}
puts(spfa() ? "YE5" : "NO");
}
return 0;
}
C. 【例题3】最优贸易
题目
思路
既然城市可以重复走,那不妨考虑tarjan缩点,生成一个DAG,min[i]表示一号点到i点的最低商品价格,记\(ans_i=price_i-min_i\),(\(price_i\)表示\(i\)城市的水晶球价格)一号点到n号点路径上\(ans\)的最大值即为答案.
这是大体思路,借助这个思路,其实不用写完整tarjan+拓扑,直接从n出发递归遍历全图并传递\(ans\)值(带上记忆化)应该也可(本人未写)
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define N 100010
#define M 1000010
int read() {
int re = 0;
bool sig = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-')
sig = 1;
c = getchar();
}
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0' , c = getchar();
return sig ? -re : re;
}
struct node {
int to , nxt;
}EDGE[2][M];
int HEAD[2][N];
int price[N];
int maxp[N] , minp[N];
node *ed;
int *head;
void addedge(int u , int v) {
static int cnt = 0;
if(u == v && u == 0) {cnt = 0; return;}
++cnt;
ed[cnt].to = v , ed[cnt].nxt = head[u] , head[u] = cnt;
}
int n , m;
int n2;
int low[N] , dfn[N] , col[N];
int stack[N] , top;
int max2[N] , min2[N];
void tarjan(int x) {
static int Time = 0;
dfn[x] = low[x] = ++Time;
stack[++top] = x;
for(int i = head[x] ; i ; i = ed[i].nxt) {
int to = ed[i].to;
if(dfn[to] == 0) {
tarjan(to);
if(low[to] < low[x])
low[x] = low[to];
}
else if(col[to] == 0)
if(low[to] < low[x])
low[x] = low[to];
}
if(low[x] == dfn[x]) {
col[x] = ++n2;
min2[n2] = max2[n2] = maxp[n2] = minp[n2] = price[x];
while(stack[top] != x) {
int y = stack[top];
col[y] = n2;
if(price[y] < minp[n2]) min2[n2] = minp[n2] = price[y];
if(price[y] > maxp[n2]) max2[n2] = maxp[n2] = price[y];
--top;
}
--top;
}
}
int ind[N];
int ans[N];
#define min_(_ , __) ((_) < (__) ? (_) : (__))
#define max_(_ , __) ((_) > (__) ? (_) : (__))
int main() {
ed = EDGE[0] , head = HEAD[0];
n = read() , m = read();
for(int i = 1 ; i <= n ; i++)
price[i] = read();
for(int i = 1 ; i <= m ; i++) {
int u = read() , v = read();
addedge(u , v);
if(read() == 2)
addedge(v , u);
}
memset(maxp , 0 , sizeof(maxp));
memset(minp , 0x3f , sizeof(minp));
for(int i = 1 ; i <= n ; i++)
if(dfn[i] == 0)
tarjan(i);
addedge(0 , 0);
ed = EDGE[1] , head = HEAD[1];
for(int i = 1 ; i <= n ; i++)
for(int j = HEAD[0][i] ; j ; j = EDGE[0][j].nxt) {
int u = col[i] , v = col[EDGE[0][j].to];
if(u == v) continue;
else {
++ind[v];
addedge(u , v);
}
}
queue <int> q;
for(int i = 1 ; i <= n2 ; i++)
if(ind[i] == 0)
q.push(i);
while(!q.empty()) {
int k = q.front();
q.pop();
if(maxp[k] - minp[k] > ans[k])
ans[k] = maxp[k] - minp[k];
for(int i = head[k] ; i ; i = ed[i].nxt) {
int to = ed[i].to;
if(--ind[to] == 0) q.push(to);
if(minp[k] < minp[to])
minp[to] = minp[k];
if(ans[k] > ans[to])
ans[to] = ans[k];
}
}
cout << ans[col[n]];
return 0;
}
D. 【例题4】汽车加油
题目
思路
别看这题是紫的,还是挺好做的
把图看成\(n\cdot n \cdot (k+1)\)个点,\((x,y,res)\)表示当前处地图的\((x,y)\)处,还可以走\(res\)步(\(res\in [0,k],res\in \Z\)),连边情况具体看题目
直接跑最短路即可
代码
AC代码
这里采用dijskar
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int read() {
int re = 0;
char c = getchar();
bool sig = false;
while(c < '0' || c > '9') {
if(c == '-') sig = true;
c = getchar();
}
while(c >= '0' && c <= '9')
re = (re << 1) + (re << 3) + c - '0',
c = getchar();
return sig ? -re : re;
}
struct node {
int x , y , cost , res;
bool operator < (const node &b) const{
return cost > b.cost;
}
}t;
inline node pus(int x , int y , int res , int cost) {
node tmp;
tmp.x = x , tmp.y = y , tmp.res = res , tmp.cost = cost;
return tmp;
}
priority_queue <node> q;
#define N 110
int n , k , a , b , c;
bool map[N][N];
int dist[N][N][15];
const int f[4][2] = {0,1 , 0,-1 , 1,0 , -1,0};
int main() {
n = read() , k = read() , a = read() , b = read() , c = read();
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
map[i][j] = read();
memset(dist , -1 , sizeof(dist));
q.push(pus(1 , 1 , k , 0));
while(!q.empty()) {
t = q.top();
q.pop();
if(dist[t.x][t.y][t.res] != -1)
continue;
dist[t.x][t.y][t.res] = t.cost;
for(int i = 0 ; i < 4 ; i++) {
int gx = t.x + f[i][0] , gy = t.y + f[i][1] , cost = t.cost + (gx < t.x || gy < t.y ? b : 0) , res = t.res - 1;
if(gx <= 0 || gy <= 0 || gx > n || gy > n) continue;
if(map[t.x][t.y])
res = k - 1 , cost += a;
if(res >= 0) if(dist[gx][gy][res] == -1)q.push(pus(gx , gy , res , cost));
if(!map[t.x][t.y])
if(dist[gx][gy][k] == -1)q.push(pus(gx , gy , k - 1 , cost + a + c));
}
}
int ans = 0x7fffffff;
for(int i = 0 ; i <= k ; i++){
if(dist[n][n][i] != -1 && dist[n][n][i] < ans)
ans = dist[n][n][i];
}
cout << ans;
// cout << dist[1][3][0] << endl;
return 0;
}
随机数据
#include <bits/stdc++.h>
using namespace std;
int random(int r , int l = 1) {
return (long long) rand() * rand() * rand() % (r - l + 1) + l;
}
int main() {
unsigned seed;
cin >> seed;
seed *= time(0);
srand(seed);
int n = random(100 , 3);
printf("%d %d %d %d %d\n" , n , random(10 , 2) , random(10) , random(10) , random(10));
for(int i = 1 ; i <= n ; i++) {
for(int j = 1 ; j <= n ; j++)
putchar(i == 1 && j == 1 || i == n && j == n ? '0' : (random(4 , 1) == 1 ? '0' : '1')) , putchar(' ');
putchar('\n');
}
return 0;
}