题意
编号为 1..N 的人, 每人有一个数;
需要满足
dj - di <= c
求1号的数与N号的数的最大差值.(略坑: 1 一定要比 N 大的...difference...不是"差别", 而是"做差"....)
思路
差分约束
差分约束顾名思义就是以"差值"作为约束条件的规划问题. 这个"差值"的特点使得这个问题可以转化为最短路问题(或最长路?)
由于SFPA(或Dijkstra)中的松弛操作:
d[v] <= d[i] + w;
移项之后可以得到
d[v] - d[u] <= w;
这和差分约束的方程形式相同. 并且也满足左边为未知量, 右边为常量; 于是可以建立有向图来解决这个问题.
将未知量设为顶点, 右边常量设为边权; 按照最短路问题的模型, 顶点的值即其到源的距离.则自然有"源"的值为0.
在差分约束系统中, 若有一组解X, 则X + k(任意实数)也为一组解.因为限制条件是"差值".
对应图的模型: 对于这样一组顶点, 源的选择会改变顶点的值, 但不会改变顶点的差值. <暂时没有更精确的理解>
本题中要求1号顶点和N号顶点的最大差值,感觉是"求最长路",为啥用一个求最短路的方法呢?
其实是在于两个问题的关系.
对于差分约束的方程组, 不等式可以全部都不取等号.
而最短路中不等式的用途则是不断调整各个变量的值, 使其对于每一个不等式(限制), 都取满足它的"上界", 即松弛操作. 对应实际操作就是选择一条路.
对于每一条和这个点相连的路, 都会被询问一遍, 如果有更短的路, 就选择新的路. 即是如果发现新的限制条件, 就要[至少]满足(取等号,"上界").
当所有的路都被询问, 亦即所有的限制条件都被满足之时, 得到的就是各个点的最短路长.
对于差分约束系统来说, 则是得到了使得每个约束条件中的两个值的差尽可能大的一组解. 当然对于1 和N来说, d[N] - d[1]是最大的.
取源为1时, d[N]即为答案.
如果要求在同一组约束之下1号和N号的最小差值, 则需要将不等式变形为
d[v] - d[u] >= w;
连接 u -> v 的边, 边权为 w, 求最长路(只要将松弛操作改一下即可). 这样就得到了使得约束条件中的两个值的差尽可能小的一组解.
这是SPFA + stack. 看题解说queue会TLE, 就没有尝试了...
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int MAXN = 30005;
const int MAXE = 150005;
const int INF = 0x3f3f3f3f;
struct pool
{
int v,pre,w;
} p[MAXE];
int num,head[MAXN],d[MAXN],n,m;
bool inq[MAXN];
stack<int> s;
void clear()
{
while(!s.empty()) s.pop();
memset(head,0,sizeof(head));
memset(d,0x3f,sizeof(d));
memset(inq,false,sizeof(inq));
num = 0;
} int SPFA()
{
d[1] = 0;
inq[1] = true;
s.push(1);
while(!s.empty())
{
int u = s.top();
s.pop();
inq[u] = 0;
for(int tmp=head[u],v;v=p[tmp].v,tmp;tmp=p[tmp].pre)
{
int w = p[tmp].w;
if(d[v]>d[u]+w)
{
d[v] = d[u] + w;
if(!inq[v])
{
inq[v] = true;
s.push(v);
}
}
}
}
return d[n];
} void add(int u, int v ,int w)
{
p[++num].v = v;
p[num].w = w;
p[num].pre = head[u];
head[u] = num;
} int main()
{
while(scanf("%d %d",&n,&m)==2)
{
clear();
while(m--)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
add(u, v, w);
}
printf("%d\n",SPFA());
}
}
Dijkstra + priority_queue
那个排序, 用了long long + 位运算排的序orz..
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 30005;
const int MAXE = 150005;
typedef long long ll;
struct pool
{
int v,pre,w;
}p[MAXE]; int num,head[MAXN],d[MAXN],m,n;
bool vis[MAXN];
priority_queue < ll, vector<ll>, greater<ll> > pq; void clear()
{
memset(head,0,sizeof(head));
memset(d,0x3f,sizeof(d));
memset(vis,false,sizeof(vis));
num = 0;
while(!pq.empty()) pq.pop();
} void add(int u, int v, int w)
{
p[++num].v = v;
p[num].w = w;
p[num].pre = head[u];
head[u] = num;
} int Dijkstra()
{
d[1] = 0;
pq.push((((ll)d[1])<<32)+1);
// printf("push d[1] = 0\n");
while(!pq.empty())
{
ll t = pq.top(); pq.pop();
int k = t & ((1ll<<32)-1);
// printf("pop d[%d] = %d\n",k,d[k]);
if(k==n) return d[n];
if(vis[k]) continue;
vis[k] = true;
for(int tmp=head[k],v,w;v=p[tmp].v,w=p[tmp].w,tmp;tmp=p[tmp].pre)
{
if(d[v]>d[k]+w)
{
d[v] = d[k] + w;
// printf("push d[%d] = %d\n",v,d[v]);
pq.push((((ll)d[v])<<32)+v);
}
}
}
return d[n];
} int main()
{
while(scanf("%d %d",&n,&m)==2)
{
int u,v,w;
clear();
for(int i=0;i<m;i++)
{
scanf("%d %d %d",&u,&v,&w);
add(u,v,w);
}
printf("%d\n",Dijkstra());
}
}