$$\color{Purple}{kuangbin题解目录}$$
描述
有 $n$ 个小朋友,编号 $1 \\sim n$。
老师要给他们发糖果。
小朋友们的攀比心都很重,现在给出 $m$ 条攀比信息。
每条信息包含三个整数 $a,b,c$,含义是小朋友 $a$ 认为小朋友 $b$ 的糖果数量最多只可以比他多 $c$ 个,否则他就生气。
老师在发糖果时,必须照顾所有小朋友的情绪,让他们都感到满意。
请问,小朋友 $n$ 最多比小朋友 $1$ 多分到多少个糖果。
输入格式
第一行包含两个整数 $n,m$。
接下来 $m$ 行,每行包含三个整数 $a,b,c$,表示一条攀比信息。
输出格式
一个整数,表示小朋友 $n$ 最多比小朋友 $1$ 多分到的糖果数量的最大可能值。
数据范围
$2 \\le n \\le 30000$,
$1 \\le m \\le 150000$,
$1 \\le a,b \\le n$,
$1 \\le c \\le 10000$。
保证一定有解。
输入样例:
2 2
1 2 5
2 1 4
输出样例:
5
思路
- 题目中求小朋友$n$最多比小朋友$1$多分到多少个糖果,可转移成
dist[n]-dist[1]>=k
,将dist[1]
移项后,变化为dist[n]>=dist[1]+k
,形如单源最短路问题
中的式子,故问题可转化为建立起点为$a$,终点为$b$,边权为$c$的有向图,跑一遍dijkstra算法
求出起点为$1$的单源最短路,最后输出dist[n]
即可.- 另外,该题可考虑采用
差分约束
来解决,当问题转化为形如一组$\color{Pink}{x_i-x’_i<=c_i}$或者$\color{Gold}{x_i-x’_i>=c_i}$,求任一满足的可行解的问题时,可以将其转化为最短路/最长路问题
.- 求两个变量差的
最大值
,那么需要将所有不等式转变成$\color{MediumSpringGreen}{\le}$的形式,建图后求最短路
;相反,如果需要求两个变量差的最小值
,那么需要将所有不等式转化成$\color{GoldEnrod}{\ge}$的形式,建图后求最长路
.- $Acwing$中会卡
栈+spfa
,$Poj$会卡队列+spfa
、卡输入
和有关make_pair()与{}
的编译问题.
代码
Dijkstra算法
// Problem: 糖果
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4250/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// Date: 2023-01-26 20:48:55
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 30010
#define MAXM 150010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,m;
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
int dist[MAXN],vis[MAXN];
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
void dijkstra(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
priority_queue<PII,vector<PII>,greater<PII> > q;
dist[start]=0;
q.push({0,start});
//q.push(make_pair(0,start));
while(q.size()>0)
{
PII temp=q.top();
q.pop();
int temp_dis=temp.first,temp_pos=temp.second;
if(vis[temp_pos]==1)
continue;
vis[temp_pos]=1;
for(int i=head[temp_pos];i!=-1;i=nex[i])
{
int j=ed[i];
if(vis[j]==1)
continue;
if(dist[j]>temp_dis+val[i])
{
dist[j]=temp_dis+val[i];
q.push({dist[j],j});
//q.push(make_pair(dist[j],j));
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
scanf("%d %d",&n,&m);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
}
dijkstra(1);
printf("%d\n",dist[n]);
return 0;
}
差分约束
// Problem: 糖果
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4250/
// Memory Limit: 64 MB
// Time Limit: 3000 ms
// Date: 2023-01-26 20:48:55
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#define MAXN 30010
#define MAXM 150010
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,m;
int head[MAXN],ed[MAXM],nex[MAXM],val[MAXM],idx;
int dist[MAXN],vis[MAXN],cnt[MAXN];
void add(int a,int b,int c)
{
ed[idx]=b;
val[idx]=c;
nex[idx]=head[a];
head[a]=idx++;
}
int spfa(int start)
{
memset(dist,0x3f,sizeof(dist));
dist[start]=0;
queue<int> q;
//stack<int> q;
dist[start]=0;
vis[start]=1;
q.push(start);
while(q.size()>0)
{
int temp=q.front();
//int temp=q.top();
q.pop();
vis[temp]=0;
for(int i=head[temp];i!=-1;i=nex[i])
{
int j=ed[i];
if(dist[j]>dist[temp]+val[i])
{
dist[j]=dist[temp]+val[i];
cnt[j]=cnt[temp]+1;
if(cnt[j]>=n)
return 1;
if(vis[j]==0)
{
vis[j]=1;
q.push(j);
}
}
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
scanf("%d %d",&n,&m);
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
}
spfa(1);
printf("%d\n",dist[n]);
return 0;
}