题目概述
有n个人和m个要求，每个要求格式形如：A认为B拿到的糖果数不应该比他多C。问最大的糖果数差距。
解题报告
这道题就是最经典的差分约束系统，由于要求差距最大，所以我们将一个点设为0，其他点设为INF刷即可。 这道题竟然卡spfa！由于按照题意没有负权边，所以用dij+heap就可以愉快的A掉此题。
示例程序
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=
30000,maxm=
150000;
int n,m,dis[maxn+
5];
int E,lnk[maxn+
5],son[maxm+
5],nxt[maxm+
5],w[maxm+
5];
bool vis[maxn+
5];
struct data {
int id,x;
bool operator < (
const data &c)
const {
return x>c.x;}};
priority_queue<data> heaps;
void Add(
int x,
int y,
int z) {son[++E]=y;w[E]=z;nxt[E]=lnk[x];lnk[x]=E;}
int Dij()
{
memset(vis,
0,
sizeof(vis));
memset(dis,
63,
sizeof(dis));
while (!heaps.empty()) heaps.pop();
heaps.push((data){
1,
0});dis[
1]=
0;
while (!heaps.empty())
{
int x=heaps.top().id;heaps.pop();
while (vis[x]&&!heaps.empty()) x=heaps.top().id,heaps.pop();
if (vis[x])
break;vis[x]=
true;
for (
int j=lnk[x];j;j=nxt[j])
if (!vis[son[j]]&&dis[x]+w[j]<dis[son[j]])
dis[son[j]]=dis[x]+w[j],heaps.push((data){son[j],dis[son[j]]});
}
int ans=
0;
for (
int i=
1;i<=n;i++) ans=max(ans,dis[i]-dis[
1]);
return ans;
}
int main()
{
freopen(
"program.in",
"r",stdin);
freopen(
"program.out",
"w",stdout);
scanf(
"%d%d",&n,&m);
for (
int i=
1,x,y,z;i<=m;i++)
scanf(
"%d%d%d",&x,&y,&z),Add(x,y,z);
return printf(
"%d\n",Dij()),
0;
}
