题目链接
参考博客
差分约束算法学习：
夜深人静写算法
模板
建图方法
In most recipes, certain tasks have to be done before others. For each task, if we are given a list of
other tasks that it depends on, then it is relatively straightforward to come up with a schedule of tasks
that satisfies the dependencies and produces a stunning dish. Many of us know that this can be solved
by some algorithm called toplogical sort.
But life is not so easy sometimes. For example, here is a recipe for making pizza dough:
1. Mix the yeast with warm water, wait for 5 to 10 minutes.
2. Mix the the remaining ingredients 7 to 9 minutes.
3. Mix the yeast and the remaining ingredients together for 10 to 15 minutes.
4. Wait 90 to 120 minutes for the dough to rise.
5. Punch the dough and let it rest for 10 to 15 minutes.
6. Roll the dough.
In this case, tasks 1 and 2 may be scheduled after the first minute (we always spend the first minute
to read the recipe and come up with a plan). The earliest task 3 may be started is at 8 minutes, and
task 4 may start at 18 minutes after the start, and so on. This recipe is relatively simple, but if some
tasks have many dependent tasks then scheduling can become unmanageable. Sometimes, the recipe
may in fact be impossible to execute.
For example, consider the following abstract recipe:
1. task 1
2. after task 1 but within 2 minutes of it, do task 2
3. at least 3 minutes after task 2 but within 2 minutes of task 1, do task 3
In this problem, you are given a number of tasks. Some tasks are related to another based on their
starting times. You are asked to assign a starting time to each task to satisfy all constraints if possible,
or report that no valid schedule is possible.
Input
The input consists of a number of cases. The first line of each case gives the number of tasks n
(1 ≤ n ≤ 100). This is followed by a line containing a non-negative integer m giving the number of
constraints. Each of the next m lines specify a constraint. The two possible forms of constraints are:
task i starts at least A minutes later than task j
task i starts within A minutes of the starting time of task j
where i and j are the task numbers of two different tasks (1 ≤ i, j ≤ n), and A is a non-negative integer
(A ≤ 150). The first form states that task i must start at least A minutes later than the start time of
task j. The second form states that task i must start no earlier than task j, and within A minutes of
the starting time of task j. There may be multiple constraints involving the same pair of tasks.
Note that at least and within include the end points (i.e. if task 1 starts at 1 minute and task 2
starts at 4 minutes, then task 2 starts at least 3 minutes later than task 1, and within 3 minutes of the
starting time of task 1).
The input is terminated by n = 0.
Output
For each case, output a single line containing the starting times of task 1 through task n separated by a
single space. Each starting time should specify the minute at which the task starts. The starting time
of each task should be positive and less than 1000000. There may be many possible schedules, and any
valid schedule will be accepted. If no valid schedule is possible, print ‘Impossible.’ on a line instead.
Sample Input
6
10
task 3 starts at least 5 minutes later than task 1
task 3 starts within 10 minutes of the starting time of task 1
task 3 starts at least 7 minutes later than task 2
task 3 starts within 9 minutes of the starting time of task 2
task 4 starts at least 10 minutes later than task 3
task 4 starts within 15 minutes of the starting time of task 3
task 5 starts at least 90 minutes later than task 4
task 5 starts within 120 minutes of the starting time of task 4
task 6 starts at least 10 minutes later than task 5
task 6 starts within 15 minutes of the starting time of task 5
3
4
task 2 starts at least 0 minutes later than task 1
task 2 starts within 2 minutes of the starting time of task 1
task 3 starts at least 3 minutes later than task 2
task 3 starts within 2 minutes of the starting time of task 1
0
Sample Output
3 1 8 18 108 118
Impossible.
题意：
有n个任务 m个限制条件
1、task i starts at least A minutes later than task j
表示 i - j >= A
2、task i starts within A minutes of the starting time of task j
表示 i - j <= A
问：每个任务开始的时间。 求一个任意解
思路：
差分约束，对于不等式形如：
点u，v ： 常数C
有： u - v <= C
则从v->u 连一条长度为C的边。
若有负环则差分约束无解。否则就能求得一个任意解。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 20009;
const int inf= 0x3f3f3f3f;
int cnt= 0,n,m ;
int head[maxn];
struct node
{
int u,v,w,next;
}edge[maxn];
void addedge(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++;
}
char s[50];
void eat(int m)
{
while(m--)
{
scanf("%s",s);
}
}
int dist[maxn],tim[maxn];
int vis[maxn];
bool spfa()
{
//memset(dist,inf,sizeof(dist));
memset(vis,0,sizeof vis);
memset(tim,0,sizeof tim);
dist[0] = 0;
for(int i=1;i<=n;i++)
{
dist[i] = inf;
addedge(0,i,0);
}
queue<int>o;
o.push(0);
while(!o.empty())
{
int u = o.front();
o.pop();
vis[u] = 0;
for(int i=head[u];~i;i=edge[i].next)
{
int v= edge[i].v;
int w =edge[i].w;
if(dist[v]>dist[u]+w)
{
dist[v] = dist[u]+w;
if(!vis[v])
{
vis[v] = 1;
tim[v]++;
o.push(v);
if(tim[v]>n)return false;
}
}
}
}
return true;
}
void solve()
{
if(spfa()==false)
{
puts("Impossible.");
return;
}
int mmin = dist[1];
for(int i=2;i<=n;i++)
{
mmin = min(mmin,dist[i]);
}
mmin = -mmin+1;
int top = 1;
for(int i=1;i<=n;i++)
{
if(top)top =0;
else printf(" ");
printf("%d",dist[i]+mmin);
}
printf("\n");
//dist[n]==inf 则有无数组解
//出现负环则无解
//否则取最小的一组解,最小的那个开始时间
}
int main()
{
while(cin>>n)
{
if(n==0)break;
scanf("%d",&m);
cnt =0 ;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
int u,v,w;
eat(1);
scanf("%d",&u);
eat(2);
if(s[0]=='a')
{
eat(1);
scanf("%d",&w);
eat(4);
scanf("%d",&v);
//u-v>=w
addedge(u,v,-w);
}
else
{
scanf("%d",&w);
eat(7);
scanf("%d",&v);
addedge(v,u,w);
addedge(u,v,0);
}
}
solve();
}
return 0;
}总结：
差分约束关键要点：
1： 对于每个不等式 x[i] - x[j] <= a[k]，对结点 j 和 i 建立一条 j -> i的有向边，边权为a[k]，求x[n-1] - x[0] 的最大值就是求 0 到n-1的最短路。
2： 学会变形 ：
如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成”<=”的形式，建图后求最短路；相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成”>=”，建图后求最长路。
如果有形如：A - B = c 这样的等式，我们可以将它转化成以下两个不等式：
A - B >= c (1)
A - B <= c (2)
再通过上面的方法将其中一种不等号反向，建图即可。
最后，如果这些变量都是整数域上的，那么遇到A - B < c这样的不带等号的不等式，我们需要将它转化成”<=”或者”>=”的形式，即 A - B <= c - 1
例如 A-B>=c
我们转化成 B-A<=-c
即建一条从A到B的权值为-c的边
3：A-B<=c注意是否需要加一个不等式A>=B，
即addedge(A,B,0)
4：注意答案，如果spfa 过程中出现负环，则说明无解
若dist[n]==inf 则说明方程有任意解
只要方程有解，就一定有无数解，但存在一个最小解
5: 像本题一样，有些方程解可能不是题目要求的解，因此需要做一下转换，因为本题是求的做任务的时间，因此任务之间具有相对性，只需要把时间最小的那个解找出来，然后设为1，其余任务的时间都是在此任务的基础上后延的
京公网安备 11010502036488号