当前位置:网站首页>Extension of graph theory
Extension of graph theory
2022-07-06 04:46:00 【Zqchang】
Super source
This topic is the template question
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 20010, INF = 0x3f3f3f3f;
int n, m, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], q[N];
bool st[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void spfa()
{
int scnt;
scanf("%d", &scnt);
memset(dist, 0x3f, sizeof dist);
int hh = 0, tt = 0;
while (scnt -- )
{
int u;
scanf("%d", &u);
dist[u] = 0;
q[tt ++ ] = u;
st[u] = true;
}
while (hh != tt)
{
int t = q[hh ++ ];
if (hh == N) hh = 0;
st[t] = false;
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q[tt ++ ] = j;
if (tt == N) tt = 0;
st[j] = true;
}
}
}
}
}
int main()
{
while (scanf("%d%d%d", &n, &m, &T) != -1)
{
memset(h, -1, sizeof h);
idx = 0;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
spfa();
if (dist[T] == INF) dist[T] = -1;
printf("%d\n", dist[T]);
}
return 0;
}
Demolition point ( Hierarchical graph )
Saving Private Ryan
state It's like pressing that feeling
In fact, the disassembly point is an additional one-dimensional state , Added some restrictions
In the shortest circuit , All problems that need to be broken down or layered , You can use it first dp To consider , The other way is , Consider the current state , Which statuses can be updated .
All the problems in the shortest circuit , The second one is more intuitive , Because the second is closer to the shortest path model
That is, consider which states can be updated by the current state
One more key is sure to pay off , So if you have a key, use it
dp There are two ways to calculate the state in , The first is to calculate the current state , Which states can be changed
Although it works dp Think about it , But it doesn't work dp Do it with your mind , because dp You need a topological order , But there may be rings in this topic
dp It can be regarded as the shortest path on the topology
In this way, it can be seen that there are only 0 and 1 Two kinds of weights , Then you can search widely with double ended queues
When running the shortest way , For convenience , A two-dimensional coordinate can be mapped into a one-dimensional , Pictured
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#include <set>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 11, M = 360, P = 1 << 10;
int n, m, k, p;
int h[N * N], e[M], w[M], ne[M], idx;
int g[N][N], key[N * N];// Number the points , Record where the key is located
int dist[N * N][P];// Record the minimum number of steps used in this state of this point
bool st[N * N][P];// Judge whether this state of this point has been used
set<PII> edges;
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void build()
{
int dx[4] = {
-1, 0, 1, 0}, dy[4] = {
0, 1, 0, -1};
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
for (int u = 0; u < 4; u ++ )
{
int x = i + dx[u], y = j + dy[u];
if (!x || x > n || !y || y > m) continue;
int a = g[i][j], b = g[x][y];
if (!edges.count({
a, b})) add(a, b, 0);// No doors and walls , There is a two-way side
}
}
int bfs()
{
memset(dist, 0x3f, sizeof dist);
dist[1][0] = 0;
deque<PII> q;
q.push_back({
1, 0});
while (q.size())
{
PII t = q.front();
q.pop_front();
if (st[t.x][t.y]) continue;
st[t.x][t.y] = true;
if (t.x == n * m) return dist[t.x][t.y];
if (key[t.x])
{
int state = t.y | key[t.x];
if (dist[t.x][state] > dist[t.x][t.y])
{
dist[t.x][state] = dist[t.x][t.y];
q.push_front({
t.x, state});
}
}
for (int i = h[t.x]; ~i; i = ne[i])
{
int j = e[i];
if (w[i] && !(t.y >> w[i] - 1 & 1)) continue; // There is a door and no key
if (dist[j][t.y] > dist[t.x][t.y] + 1)
{
dist[j][t.y] = dist[t.x][t.y] + 1;
q.push_back({
j, t.y});
}
}
}
return -1;
}
int main()
{
cin >> n >> m >> p >> k;
for (int i = 1, t = 1; i <= n; i ++ )// Initialize node number
for (int j = 1; j <= m; j ++ )
g[i][j] = t ++ ;
memset(h, -1, sizeof h);
while (k -- )
{
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
int a = g[x1][y1], b = g[x2][y2];// Find the number corresponding to two points
edges.insert({
a, b}), edges.insert({
b, a});// It means there is a wall or door here
if (c) add(a, b, c), add(b, a, c);// Building a door , The wall cannot be passed , So just mark , Do not build edges
}
build();// Establish the remaining edges
int s;
cin >> s;
while (s -- )
{
int x, y, c;
cin >> x >> y >> c;
key[g[x][y]] |= 1 << c - 1;// Record key
}
cout << bfs() << endl;
return 0;
}
Use dp Thought counting class of
dp It can be roughly regarded as the shortest path running on the topology
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = 400010, mod = 100003;
int n, m;
int h[N], e[M], ne[M], idx;
int dist[N], cnt[N];
int q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
cnt[1] = 1;
int hh = 0, tt = 0;
q[0] = 1;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + 1)
{
dist[j] = dist[t] + 1;
cnt[j] = cnt[t];
q[ ++ tt] = j;
}
else if (dist[j] == dist[t] + 1)// It can be seen here as a state transition equation
{
cnt[j] = (cnt[j] + cnt[t]) % mod;
}
}
}
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
bfs();
for (int i = 1; i <= n; i ++ ) printf("%d\n", cnt[i]);
return 0;
}
The meaning of this topic is probably , Give you the starting point and the ending point , Ask you how many shortest paths there are at most , If the secondary short circuit is more than the shortest one 1, Then add the number of short circuits last time
Open one-dimensional storage times more short circuit , And then like dp Same as dij Update inside
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010, M = 20010;
struct Ver
{
int id, type, dist;
bool operator> (const Ver &W) const
{
return dist > W.dist;
}
};
int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2], cnt[N][2];
bool st[N][2];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
memset(cnt, 0, sizeof cnt);
dist[S][0] = 0, cnt[S][0] = 1;
priority_queue<Ver, vector<Ver>, greater<Ver>> heap;
heap.push({
S, 0, 0});
while (heap.size())
{
Ver t = heap.top();
heap.pop();
int ver = t.id, type = t.type, distance = t.dist, count = cnt[ver][type];
if (st[ver][type]) continue;
st[ver][type] = true;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j][0] > distance + w[i])
{
dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];
heap.push({
j, 1, dist[j][1]});
dist[j][0] = distance + w[i], cnt[j][0] = count;
heap.push({
j, 0, dist[j][0]});
}
else if (dist[j][0] == distance + w[i]) cnt[j][0] += count;
else if (dist[j][1] > distance + w[i])
{
dist[j][1] = distance + w[i], cnt[j][1] = count;
heap.push({
j, 1, dist[j][1]});
}
else if (dist[j][1] == distance + w[i]) cnt[j][1] += count;
}
}
int res = cnt[T][0];
if (dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];
return res;
}
int main()
{
int cases;
scanf("%d", &cases);
while (cases -- )
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
idx = 0;
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
scanf("%d%d", &S, &T);
printf("%d\n", dijkstra());
}
return 0;
}
边栏推荐
- Selection of slow motion function
- 牛顿插值法
- Sorting out the latest Android interview points in 2022 to help you easily win the offer - attached is the summary of Android intermediate and advanced interview questions in 2022
- DMA use of stm32
- Knowledge consolidation source code implementation 3: buffer ringbuffer
- win10电脑系统里的视频不显示缩略图
- View workflow
- ue5 小知识 FreezeRendering 查看视锥内渲染的物体
- [Zhao Yuqiang] deploy kubernetes cluster with binary package
- How to realize automatic playback of H5 video
猜你喜欢
二叉树基本知识和例题
canal同步mysql数据变化到kafka(centos部署)
[mathematical modeling] differential equation -- sustainable development of fishing industry
Canal synchronizes MySQL data changes to Kafka (CentOS deployment)
Orm-f & Q object
【LGR-109】洛谷 5 月月赛 II & Windy Round 6
The underlying structure of five data types in redis
Easyrecovery reliable and toll free data recovery computer software
Redis - redis in action - redis actual combat - actual combat Chapter 1 - SMS login function based on redis - redis + token shared session application - with code
SQL injection vulnerability (MSSQL injection)
随机推荐
Codeforces Round #804 (Div. 2)
[mathematical modeling] differential equation -- sustainable development of fishing industry
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Visio draw fan
二叉树基本知识和例题
Platformio create libopencm3 + FreeRTOS project
CADD课程学习(7)-- 模拟靶点和小分子相互作用 (柔性对接 AutoDock)
After learning classes and objects, I wrote a date class
Canal synchronizes MySQL data changes to Kafka (CentOS deployment)
Postman关联
MPLS experiment
最高法院,离婚案件判决标准
CADD course learning (8) -- virtual screening of Compound Library
Lagrange polynomial
Sorting out the latest Android interview points in 2022 to help you easily win the offer - attached is the summary of Android intermediate and advanced interview questions in 2022
11. Intranet penetration and automatic refresh
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
[Yu Yue education] reference materials of complex variable function and integral transformation of Northwestern Polytechnic University
几种RS485隔离通讯的方案介绍
The IPO of mesk Electronics was terminated: Henan assets, which was once intended to raise 800 million yuan, was a shareholder