[problem solution] P1073 [NOIP2009 improvement group] optimal trade (graph theory, shortest path, SPFA)

[problem solution] P1073 [NOIP2009 improvement group] optimal trade

This question is wonderful!

Although this is only a green question, it still stuck me for a long time. The main reason is that there are two ideas in this question, which I totally didn't think of. I'm too hungry

Write down ideas to record this wonderful topic.

Title Link

[NOIP2009 improvement group] optimal trade - Luogu

Summary of topic meaning

There is a graph with \ (n \) points \ (m \) edges, some of which are bidirectional edges and some are unidirectional edges. Each point \ (I \) has a point weight \ (p_i \), and it is required to find a path from 1 to \ (n \) on this figure, so that the path can pass through two points \ (s,t \) (first through \ (s \) and then through \ (t \)), and the maximum value of \ (p_t-p_s \).

Train of thought analysis

first,

It is required to find a path from 1 to \ (n \), so that the path can pass through two points \ (s,t \) (first through \ (s \) and then through \ (t \)), and \ (p_t-p_s \) is the largest.

This condition can be translated into:

There is a relay node \ (K \), which is the point on the path from 1 to \ (n \), at the same time, \ (s \) is the point with the smallest point weight on the \ (1-k \) path, and \ (t \) is the point with the largest point weight on the \ (k-n \) path.

So what inspiration does this have for us?

We can find that if we find the following three, the problem will be solved:

  1. Relay node \ (k \);

  2. \(1-k \) the point with the smallest point weight on the path;

  3. \(k-n \) the point with the largest point weight on the path.

Step by step!

Relay node \ (k \)

It can be found that since \ (1-n \) has multiple paths, all points except 1 and \ (n \) may become relay nodes (nonsense), so let's enumerate this relay node.

\(1-k \) the point with the least weight on the path

We know that SPFA can find the shortest path, so can it find the point with the least weight on the path?

Actually, absolutely.

Following the practice of SPFA seeking the shortest path, we define \ (dis1_i \) to represent the weight of the node with the smallest weight in all paths from node 1 to node \ (I \). (this is the first important idea of this topic)

\The calculation method of (dis1_i \) is similar to that of single source shortest path. You only need to change \ (dis1_x+w(x,y) \) update \ (dis1_y \) to \ (\ min(dis1_x,p_y) \) update \ (dis1_y \).

Therefore, we only need to run this SPFA once with 1 as the starting point to find the point with the lowest point weight obtained by taking any other point on the \ (1-n \) path as the relay node.

\(k-n \) the point with the largest point weight on the path

Obviously, we can follow the above practice and use \ (dis2_i \) to represent the weight of the node with the largest weight in all paths from node \ (I \) to \ (n \). Then the update can also be compared with the above.

But there is a problem.

Who should we run SPFA from?

Start with \ (x \)? Obviously not\ (x \) are not sure.

So what is certain? End point \ (n \).

So we use the second important idea of this topic - inverse graph.

We can create an inverse graph: a graph obtained by reversing the directions of all edges on the basis of the original graph.

Then run SPFA again from \ (n \). So as to find all \ (dis2_i \).

Finally, enumerate each relay node \ (I \), and the answer is the minimum value of \ (dis2_i-dis1_i \) among all \ (I \).

So the problem is solved perfectly!

Solving steps

  1. For all edges entered, use two basic_string is used as the edge information of positive and negative graphs respectively. (note that both positive and negative sides should be saved once)

  2. Take \ (I \) as the starting point, run the SPFA of "shortest point weight" on the original drawing, and find all \ (dis1_i \).

  3. Take \ (n \) as the starting point and run the SPFA of "shortest point weight" on the inverse graph to find all \ (dis2_i \).

  4. Enumerate each \ (I \), then \ (ans=\min(dis2_i-dis1_i) \).

Key points

  1. Topic meaning transformation;

  2. Think of turning point weight into edge weight to run SPFA;

  3. Think of establishing inverse graph;

Among them, 2 and 3 are also the two most important ideas of this topic.

Error prone point

  1. In terms of thinking, this problem can not be solved by dijkstra, because it does not meet the greedy nature of dijkstra;

  2. In terms of code implementation, remember that \ (dis1 \) except 1 should be initialized to INF at the beginning, and \ (dis1 \) of 1 should be initialized to \ (p_1 \);

    All \ (dis2 \) except \ (n \) should be initialized to 0\ The \ (dis2 \) of (n \) is initialized to \ (p_n \).

code implementation

//luoguP1073
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
using namespace std;
const int maxn=1e5+10;
int n,m;
int p[maxn],dis1[maxn],dis2[maxn],ans;

basic_string<int>e1[maxn];
basic_string<int>e2[maxn];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void SPFA()
{
	queue<int>q;
	q.push(1);
	for(int i=2;i<=n;i++)dis1[i]=(1ll<<29)-1;
	dis1[1]=p[1];
    while(!q.empty())
    {
    	int x=q.front();
    	q.pop();
    	for(int y:e1[x])
    	{
    		if(dis1[y]>min(dis1[x],p[y]))
    		{
    			dis1[y]=min(dis1[x],p[y]);
    			q.push(y);
			}
		}
	}
	while(!q.empty())q.pop();
	q.push(n);
	dis2[n]=p[n];
	while(!q.empty())
    {
    	int x=q.front();
    	//cout<<x<<endl;
    	q.pop();
    	for(int y:e2[x])
    	{
    		//cout<<y<<endl;
    		//cout<<"ex "<<dis2[x]<<" "<<p[y]<<endl;
    		if(dis2[y]<max(dis2[x],p[y]))
    		{
    			dis2[y]=max(dis2[x],p[y]);
    			q.push(y);
			}
		}
	 } 
}

int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)p[i]=read();
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		x=read();y=read();z=read();
		if(z==1){e1[x]+=y;e2[y]+=x;}
		else
		{
			e2[x]+=y;e2[y]+=x;
			e1[x]+=y;e1[y]+=x;
		 } 
	}
	//for(int i=1;i<=n;i++)cout<<e1[i].size()<<" "<<e2[i].size()<<endl;
	SPFA();
	for(int i=1;i<=n;i++)
	{
		//cout<<dis2[i]<<" "<<dis1[i]<<endl;
		ans=max(ans,dis2[i]-dis1[i]);
	}
	cout<<ans<<endl;
} 
/*Two basic_string, SPFA twice. 
Definition dis1[i] represents the weight of the node with the smallest weight in all paths from 1 to I.
dis2[i] It represents the weight of the node with the largest weight in all paths from i to n
 Then the answer is min(dis2[i]-dis1[i]);
The broken point is the edge, and SPFA is made on the point weight.
Do it twice and get dis1[i] and dis2[i] respectively.
Wonderful!
*/ 

Tags: Graph Theory shortest path SPFA

Posted by ALEXKENT18 on Sun, 22 May 2022 03:27:34 +0300