題意：有n個任務，給出完成n個任務所需時間，以及一些任務安排。任務安排有四種：

FAS a b：任務a需在任務b開始后完成。

FAF a b：任務a需在任務b完成后完成。

SAF a b：任務a需在任務b完成后開始。

SAS a b：任務a需在任務b開始后開始。

求在這些任務安排下各個任務的最早開始時間，若任務安排為不可能安排則輸出impossible。每組數據結束需要輸出一個空行。

思路：四種任務安排可以得到四種不等式如下：（dis[]表示任務開始時間，x[]表示任務完成所需時間）

FAS a b：dis[a]+x[a]>=dis[b]

FAF a b：dis[a]+x[a]>=dis[b]+x[b]

SAF a b：dis[a]>=dis[b]+x[b]

SAS a b：dis[a]>=dis[b]

因為求任務開始的最早時間即最小值，加上此題有好多的不等式可以進行差分約束。所以建圖，spfa()最長路即可求得答案。

終于看到一個比較不那么抽象的差分約束了

記得連上超級源點0

顯然不可能有短路

當有環的時候沒有答案！

#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) // #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f #define N 100000 int head[N]; int pos; struct node {int to,v,nex; }edge[10000000]; void add(int a,int b,int c) {edge[++pos].nex=head[a];head[a]=pos;edge[pos].v=c;edge[pos].to=b; } int n;int vis[N],dis[N],cnt[N]; bool spfa() {rep(i,1,n)vis[i]=0,dis[i]=-inf,cnt[i]=0;dis[0]=0;vis[0]=1;cnt[0]++;queue<int>q;q.push(0);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=head[u];i;i=edge[i].nex){int v=edge[i].to;if(dis[v]<dis[u]+edge[i].v){dis[v]=dis[u]+edge[i].v;if(!vis[v]){if(++cnt[v]>n)return 0;vis[v]=1;q.push(v);}}}}return 1; } int t[N]; int main() {int cas=0;while(RI(n),n){printf("Case %d:\n",++cas);CLR(head,0);pos=0;rep(i,1,n)RI(t[i]);int a,b;char s[5];while(1){RS(s);if(s[0]=='#')break;RII(a,b);if(s[0]=='F'){if(s[2]=='S')add(b,a,-t[a]);elseadd(b,a,t[b]-t[a]);}else{if(s[2]=='F')add(b,a,t[b]);elseadd(b,a,0);}}rep(i,1,n)add(0,i,0);if(spfa()){rep(i,1,n)printf("%d %d\n",i,dis[i]);}elseprintf("impossible\n");cout<<endl;}return 0; } View Code

?

轉載于:https://www.cnblogs.com/bxd123/p/10780752.html

總結

以上是生活随笔為你收集整理的Schedule Problem spfa 差分约束的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。