ACM intensive training graph theory exercise 3 in the summer vacation of 2020 [problem solving]

Link to the exercise sheet

A :hdu1548 【A strange lift】 (Bfs && Dijkstra)

The main idea of the topic ： This is a story that happened in the elevator , Give the starting and ending points , It requires at least several operations to reach the destination , Give the number corresponding to each floor , This number represents the number of layers that the current layer can go up and down . Be careful , The elevator cannot exceed the end point , There is no basement , That is to say, the minimum value is 1. Find the minimum number of operations .

BFS
When I first saw this topic , Instinctive response this is a bfs The subject of , But the question is put in the list of the shortest path , The subconscious tells me , The shortest path algorithm is dijkstra, Freud ,spfa Algorithm , So I have been thinking about how to solve the shortest path … Forget the bfs You can also find the shortest path

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int vis[maxn], f[maxn];
struct node
{
    
    int x, step;
};
int n, a, b;
int bfs()
{
    
    node s, e;
    memset(vis, 0, sizeof(vis));
    queue<node> q;
    s.x = a; // Initialize the position of the starting point , Judge according to the input data 
    s.step = 0;
    q.push(s);
    while (!q.empty())
    {
    
        s = q.front();
        q.pop();
        if (s.x == b) // If you find it, go back to 
            return s.step;
        e.x = s.x + f[s.x];        // Go up 
        if (e.x <= b && !vis[e.x]) // If the current point is less than the end point , And didn't walk 1 Then it conforms to 
        {
    
            e.step = s.step + 1; // Operands plus 1
            vis[e.x] = 1;        // Mark that point has passed 
            q.push(e);           // Queue entry 
        }
        e.x = s.x - f[s.x]; // Go down （ ditto ）
        if (e.x >= 1 && !vis[e.x])
        {
    
            vis[e.x] = 1;
            e.step = s.step + 1;
            q.push(e);
        }
    }
    return -1; // Did not find 
}
int main()
{
    
    while (~scanf("%d", &n) && n)
    {
    
        scanf("%d%d", &a, &b);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &f[i]);
        printf("%d\n", bfs());
    }
}

Dijkstra
The shortest path algorithm is designed cleverly , But it is undeniable that this is still a simple version dijkstra Board topic , We need to judge whether the current layer can be moved （ Up and down ） Whether the number of layers of will cross the boundary , If there is no boundary crossing, it is a feasible solution , The shortest path of this problem is the minimum number of operations , We label every feasible solution as 1, Represents the number of times that can be operated in turn , That's why you can use bfs Why , Our goal is to find the minimum operand , That is to find out the minimum operation steps from the start point to the end point , The weight of each edge is 1！

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int dis[maxn], vis[maxn], n;
int w[maxn][maxn], a[maxn];

int dijkstra(int s, int e)
{
    
    int pos;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= n; ++i)
        dis[i] = w[s][i];// assignment , Assign the distance from the starting point to other points to dis Array 
    dis[s] = 0;
    vis[s] = 1;
    for (int i = 1; i <= n; ++i)
    {
    
        int min = inf;
        for (int j = 1; j <= n; ++j)// Each traversal will find a shortest edge and record it to facilitate subsequent relaxation operations 
        {
    
            if (dis[j] < min && !vis[j])// Determine the minimum value 
            {
    
                pos = j;
                min = dis[j];// Maintenance minimum 
            }
        }
        if (min == inf)
            break;
        vis[pos] = 1;
        for (int i = 1; i <= n; ++i)// Slack operation 
            if (dis[i] > dis[pos] + w[pos][i] && !vis[i])
                dis[i] = dis[pos] + w[pos][i];
    }
}
int main()
{
    
    int s, e;
    while (~scanf("%d", &n) && n)
    {
    
        memset(w, inf, sizeof(w));
        scanf("%d%d", &s, &e);
        for (int i = 1; i <= n; ++i)
        {
    
            scanf("%d", &a[i]);
            if (i + a[i] <= n)// Judgement boundary 
                w[i][i + a[i]] = 1;
            if (i - a[i] >= 1)// ditto 
                w[i][i - a[i]] = 1;
        }
        dijkstra(s, e);
        printf("%d\n", dis[e] == inf ? -1 : dis[e]);
    }
    return 0;
}

B hdu2544 【 shortest path 】dijkstra The template questions

ps： This is a naked dijkstra The template questions

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int a[maxn], vis[maxn], c[1010][1010], dis[maxn], n, m;
void dijkstra()
{
    
    memset(vis, 0, sizeof(vis));
    memset(dis, inf, sizeof(dis));
    for (int i = 1; i <= n; ++i)
        dis[i] = c[1][i];
    dis[1] = 0;
    vis[1] = 1;
    for (int i = 1; i <= n; ++i)
    {
    
        int min = inf;
        int pos;
        for (int j = 1; j <= n; ++j) // Find the smallest edge 
        {
    
            if (dis[j] < min && !vis[j])
            {
    
                min = dis[j]; // Maintenance minimum 
                pos = j;
            }
        }
        vis[pos] = 1;                // Mark min 
        for (int i = 1; i <= n; ++i) // Slack operation 
            if (dis[i] > dis[pos] + c[pos][i] && !vis[i])
                dis[i] = dis[pos] + c[pos][i];
    }
}
int main()
{
    
    while (~scanf("%d%d", &n, &m) && n && m)
    {
    
        memset(c, inf, sizeof(c));
        for (int i = 1; i <= m; ++i)
        {
    
            int u, v, e;
            scanf("%d%d%d", &u, &v, &e);
            c[u][v] = c[v][u] = e; // The undirected graph is stored twice 
        }
        dijkstra();
        printf("%d\n", dis[n]);
    }
    return 0;
}

C hdu2066 【 A solo trip 】 dijkstra The template questions

Topic analysis
First of all, the title does not give the corresponding number of cities , So we can go to the number of the largest city when inputting the city and let it do n, Secondly, we need to update the path weight once min Operate at a minimum （ I don't understand that ） Otherwise the code will be wrong , At the beginning, I thought that each person who is away from Xiaocao's home should take a minimum value and then traverse once to output the minimum value , But the time limit is exceeded , So we can regard the grass as the source , The distance from the source point to each adjacent point is 0, So we only need to run once dijkstra You can find the minimum value

Plain version dijkstra

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e3 + 10;
int a[maxn], vis[maxn], c[1010][1010], dis[maxn], n, m, d, b[maxn], tot;
void dijkstra()
{
    
    memset(vis, 0, sizeof(vis));
    memset(dis, inf, sizeof(dis));
    for (int i = 0; i <= tot; ++i)
        dis[i] = c[0][i];
    dis[0] = 0;
    vis[0] = 1;
    for (int i = 1; i <= tot; ++i)
    {
    
        int min = inf;
        int pos;
        for (int j = 1; j <= tot; ++j)
        {
    
            if (dis[j] < min && !vis[j])
            {
    
                min = dis[j];
                pos = j;
            }
        }
        vis[pos] = 1;
        for (int i = 1; i <= tot; ++i)
            if (dis[i] > dis[pos] + c[pos][i] && !vis[i])
                dis[i] = dis[pos] + c[pos][i];
    }
}
int main()
{
    
    while (~scanf("%d%d%d", &n, &m, &d))
    {
    
        tot = 0;
        memset(c, inf, sizeof(c));
        for (int i = 1; i <= n; ++i)
        {
    
            int u, v, e;
            scanf("%d%d%d", &u, &v, &e);
            tot = max(tot, max(u, v));
            c[u][v] = c[v][u] = min(c[u][v],e); // The undirected graph is stored twice 
        }
        for (int i = 1; i <= m; ++i)
        {
    
            scanf("%d", &a[i]);
            c[0][a[i]] = c[a[i]][0] = 0;// The distance from Xiaocao's home to each point is 0
        }
        for (int j = 1; j <= d; ++j)
            scanf("%d", &b[j]);
        int ans = inf;
        dijkstra();
        for (int j = 1; j <= d; ++j)
            ans = min(ans, dis[b[j]]);
        printf("%d\n", ans);
    }
    return 0;
}

dijkstra+ Heap optimization

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int inf = 0x3f3f3f3f;
int m, a[1005], si, ei, b[1005], n;
int vis[1005], mp[1005][1005], dis[1005];

struct node
{
    
    int id;
    int val;
    bool operator<(const node x) const
    {
    
        return val > x.val;
    }
};

void dijkstra()
{
    
    memset(vis, 0, sizeof(vis));
    memset(dis, inf, sizeof(dis));
    dis[0] = 0;
    priority_queue<node> q;
    node s, e;
    s.id = 0;
    s.val = 0;
    q.push(s);
    while (!q.empty())
    {
    
        s = q.top();
        q.pop();
        int id = s.id, val = s.val;
        vis[id] = 1;
        for (int i = 1; i <= n; i++)
        {
    
            if (!vis[i] && dis[i] > mp[id][i] + val)
            {
    
                dis[i] = mp[id][i] + val;
                e.id = i;
                e.val = val + mp[id][i];
                q.push(e);
            }
        }
    }
}

int main()
{
    
    while (~scanf("%d %d %d", &m, &si, &ei))
    {
    
        n = 0;
        memset(mp, inf, sizeof(mp));
        for (int i = 1; i <= m; i++)
        {
    
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            n = max(max(a, b), n);
            if (mp[a][b] > c)
                mp[a][b] = mp[b][a] = c;
        }
        for (int i = 1; i <= si; i++)
        {
    
            scanf("%d", &a[i]);
            mp[0][a[i]] = mp[a[i]][0] = 0;
        }
        for (int i = 1; i <= ei; i++)
            scanf("%d", &b[i]);
        dijkstra();
        int mi = inf;
        for (int i = 1; i <= ei; i++)
            mi = min(dis[b[i]], mi);
        printf("%d\n", mi);
    }
    return 0;
}

D hdu1217 【Arbitrage】 （Floyd && spfa）

The main idea of the topic ： Given several currencies and the exchange rate between each currency, you can judge whether you have made money through the conversion between currencies
PS： Do it for the first time floyd, Feeling floyd Better than other algorithms , The code is also very short ,floyd We are looking for the shortest path of multiple sources , After every update , We can calculate the conversion between any two currencies , First initialize , Between the same currency “ distance ” yes 1, Then the path is updated through conversion , It's just multiplication , After the final traversal , We find that if there is greater than between the two currencies 1 So it shows that you can make money through the conversion between exchange rates .
Quickly understand Floyd Algorithm

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e3 + 10;
double dis[maxn][maxn];
char s[maxn][maxn];
int n, m;

void floyd()
{
    
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dis[i][j] = max(dis[i][j], dis[i][k] * dis[k][j]);
}
int main()
{
    
    int cnt = 1;
    while (~scanf("%d", &n) && n)
    {
    
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dis[i][j] = i == j ? 1 : 0;
        for (int i = 1; i <= n; ++i)
            scanf("%s", s[i]);
        scanf("%d", &m);
        for (int i = 1; i <= m; ++i)
        {
    
            char s0[maxn], s1[maxn];
            double x;
            int k1, k2;
            scanf("%s%lf%s", s0, &x, s1);
            for (int j = 1; j <= n; ++j)
            {
    
                if (strcmp(s0, s[j]) == 0)
                    k1 = j;
                if (strcmp(s1, s[j]) == 0)
                    k2 = j;
            }
            dis[k1][k2] = x;
        }
        floyd();
        int flag = 0;
        for (int i = 1; i <= n; ++i)
        {
    
            if (dis[i][i] > 1.0)
            {
    
                printf("Case %d: Yes\n", cnt++);
                flag = 1;
                break;
            }
        }
        if (!flag)
            printf("Case %d: No\n", cnt++);
    }
    return 0;
}

spfa Algorithm
PS：spfa The reason why we can judge a negative ring , Because , When finding the shortest path, you can always walk through the circle with a negative ring , In this way, the shortest path can be refreshed all the time , Refresh indefinitely , This topic can be used spfa The same thing , Because it's bigger than 1 The product of the number of must be larger than the original number , The product of all existing edge weights is greater than 1 when , It is equivalent to a negative ring with a negative edge weight sum , It's a truth , As long as the judgment is greater than 1 That's it yes Otherwise, it would be no

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int n, m, tot, u, v;
double w;
struct node
{
    
	int v, next;
	double w;
} edge[maxn];
double dis[maxn];
int vis[maxn], head[maxn], cnt[maxn];
char str[maxn][maxn], buff[maxn], buff1[maxn];

int solve(char *s)
{
    
	for (int i = 1; i <= n; i++)
		if (strcmp(s, str[i]) == 0)
			return i;
	return -1;
}

void add(int u, int v, double w)
{
    
	edge[++tot].v = v;
	edge[tot].w = w;
	edge[tot].next = head[u];
	head[u] = tot;
}
int Spfa(int s)
{
    
	memset(dis, 0, sizeof dis);
	memset(vis, 0, sizeof vis);
	memset(cnt, 0, sizeof cnt);
	dis[s] = 1.0;
	vis[s] = 1;
	queue<int> q;
	q.push(s);
	while (!q.empty())
	{
    
		int e = q.front();
		q.pop();
		vis[e] = 0;
		for (int i = head[e]; ~i; i = edge[i].next)
		{
    
			int v = edge[i].v;
			if (dis[e] * edge[i].w > dis[v])
			{
    
				dis[v] = dis[e] * edge[i].w;
				if (!vis[v])
				{
    
					q.push(v);
					vis[v] = 1;
					if (++cnt[v] > n)
						break;
				}
			}
		}
	}
	if (dis[s] > 1.0)
		return 1;
	return 0;
}

int main()
{
    
	int cas = 1;
	while (scanf("%d", &n) && n)
	{
    
		tot = 0;
		memset(head, -1, sizeof head);
		for (int i = 1; i <= n; i++)
			scanf("%s", str[i]);
		scanf("%d", &m);
		for (int i = 1; i <= m; i++)
		{
    
			scanf("%s%lf%s", buff1, &w, buff);
			u = solve(buff1);
			v = solve(buff);
			add(u, v, w);
		}
		int find = 0;
		for (int i = 1; i <= n; i++)
			if (Spfa(i))
			{
    
				printf("Case %d: Yes\n", cas++);
				find = 1;
				break;
			}
		if (!find)
			printf("Case %d: No\n", cas++);
	}
	return 0;
}

E hdu 1317 【XYZZY】（floyd && spfa）

The main idea of the topic ： Yes n A room (n<=100), Each room has a point weight （ The first 1 Room and n The weight of room No. is 0）, When you arrive at the room, you will automatically get the right to this point （ May be negative ）. Give some undirected edges . There was a man , Initial energy value 100, The initial position is 1 Room number , To go to the first n Room number , And the energy value on the body shall not be less than or equal to 0. Can reach the n A room wins , Ask if you can win .

Topic analysis ： First of all, we use floyd To judge his connectivity , Then take it and run it again spfa, Note that the initial is 100
I don't understand the subject thoroughly , Here is a very detailed blog for reference only Analyze the blog in detail

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
const int inf = -0x3f3f3f3f;

int n, m;
int dis[maxn][maxn], d[maxn], mp[maxn][maxn], num[maxn], e[maxn];

void floyd()
{
    
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				dis[i][j] = dis[i][j] || (dis[i][k] && dis[k][j]);
}

int spfa(int s, int d[])
{
    
	queue<int> q;
	q.push(s);
	d[s] = 100;
	while (!q.empty())
	{
    
		int u = q.front();
		q.pop();
		num[u]++;
		if (num[u] > n)
			// If the number of times a point enters the queue is greater than or equal to n That means it's in the ring （ In fact, since the negative ring in the longest path does not cycle, this must be a positive ring ）, So as long as we can reach the destination from this point （Floyd Judge ）, Then you can win ; On the contrary, if you can't reach the end, you will lose （ Because the relaxation times are greater than or equal to n If it is not over, the longest road does not exist ）.
			return dis[u][n];
		for (int i = 1; i <= n; ++i)
			if (mp[u][i] && d[u] + e[i] > d[i] && d[u] + e[i] > 0) // If this road exists and passes through it, it will be greater than 0
			{
    
				d[i] = d[u] + e[i];
				q.push(i);
			}
	}
	return d[n] > 0; // The returned value must be greater than 0
}
int main()
{
    
	while (~scanf("%d", &n))
	{
    
		if (n == -1)
			return 0;
		memset(mp, 0, sizeof(mp));
		memset(d, inf, sizeof(d));
		memset(num, 0, sizeof(num));
		memset(dis, 0, sizeof(dis));
		for (int i = 1; i <= n; ++i)
		{
    
			scanf("%d%d", &e[i], &m);
			for (int j = 1; j <= m; ++j)
			{
    
				int v;
				scanf("%d", &v);
				mp[i][v] = 1;  // The array stores information about the edges 
				dis[i][v] = 1; // The array indicates that the two points are connected 
			}
		}
		floyd();
		if (dis[1][n] == 0) // If there is no connection between the start point and the end point, output directly 
			puts("hopeless");
		else
		{
    
			if (spfa(1, d)) // If connected and the value is greater than 0 Can 
				puts("winnable");
			else // Less than zero, then not 
				puts("hopeless");
		}
	}
	return 0;
}

F hdu 1535 【Invitation Cards】 （spfa+ Optimize ）

The main idea of the topic ： Numbered 1～P The site of , Yes Q A bus route , The bus route only goes directly from one starting station to the terminal station , Is one-way , Each route has its own fare .
Yes P I'm from 1 set out , They want to get to every bus stop , And then back at night 1. Find the sum of the minimum round-trip expenses for all people .

Topic analysis ： Find the shortest path , First, find the shortest path forward and backward , What I want is 1 The sum of the shortest paths from point No. 1 to all points , After that, reverse the storage , Find the shortest path again , Because the data is large, it needs to be optimized , There is also time to use long long To define variables

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int vis[maxn], head[maxn];
ll dis[maxn];
ll cnt;
int n, m;
struct node
{
    
	int u, v, w, next;
} edge[maxn];

void add(int u, int v, int w)
{
    
	edge[++cnt].u = u;
	edge[cnt].v = v;
	edge[cnt].w = w;
	edge[cnt].next = head[u];
	head[u] = cnt;
}

int spfa(int s)
{
    
	queue<int> q;
	q.push(s);
	vis[s] = 1;
	dis[s] = 0;
	while (!q.empty())
	{
    
		int now = q.front();
		q.pop();
		vis[now] = 0;
		for (int i = head[now]; ~i; i = edge[i].next)
		{
    
			int to = edge[i].v;
			if (dis[to] > dis[now] + edge[i].w)
			{
    
				dis[to] = dis[now] + edge[i].w;
				if (!vis[to])
				{
    
					vis[to] = 1;
					q.push(to);
				}
			}
		}
	}
	ll sum = 0;
	for (int i = 1; i <= n; ++i)
		if (dis[i] != inf)
			sum += dis[i];
	return sum;
}
int main()
{
    
	int t, a, b, c;
	scanf("%d", &t);
	while (t--)
	{
    
		cnt = 0;
		memset(dis, inf, sizeof(dis));
		memset(vis, 0, sizeof(vis));
		memset(head, -1, sizeof(head));
		scanf("%d%d", &n, &m);
		for (int i = 1; i <= m; ++i)
		{
    
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c);
		}
		ll ans = spfa(1);
		cnt = 0;
		memset(dis, inf, sizeof(dis));
		memset(vis, 0, sizeof(vis));
		memset(head, -1, sizeof(head));
		for (int i = 1; i <= m; ++i)
		{
    
			a = edge[i].u;
			b = edge[i].v;
			c = edge[i].w;
			add(b, a, c);
		}
		ll ans2 = ans + spfa(1);
		printf("%lld\n", ans2);
	}
	return 0;
}

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

therefore , Oh, I see , Love will disappear one day , It's inevitable . When this feeling disappears , All that remains is mutual understanding 、 Trust each other 、 Interdependence , without , Sooner or later, it will lead to tragedy . Girls can't always lean on boys' shoulders , Boys can't always pester girls , Only two people helped each other , In order not to fall .