其实我个人的看法，觉得差分约束最难的还是要把问题的限制想全，如果遗漏了一个点肯定错，然后求最大值就是<=k1,k2,k3,因为都要满足所以肯定要求k里面的最小值，最短路，求最小值>=k1,k2,k3，就是求最大值，最长路。最短路对应负环，最长路对应正环，如果传统队列的spfa太慢那就考虑把队列换成栈，不过一般情况下不要乱用，在更新值的方面，队列比栈要快不少。
模板题，看清楚题目问的最值是最小还是最大，该题是最小那么我们求最长路，最长路对应的是>=，即a>=b+w，a,b分别为端点，w为边权，如果存在正环就输出无解。
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=N*3;
int h[N],q[N],w[M],idx,e[M],ne[M];
int dist[N];
bool st[N];
int cnt[N];
int n,k;
void add(int a,int b,int c)
{
e[idx] =b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int spfa()
{
int tt=0,hh=0;
memset(dist,-0x3f,sizeof dist);
dist[0]= 0;
q[tt++]=0;
st[0]=true;
while(tt!=hh)
{
int t=q[--tt];
st[t]=false;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(dist[j]<dist[t]+w[i])
{
dist[j] = dist[t] +w[i];
cnt[j] =cnt[t] +1;
if(cnt[j]>=n+1) return -1;
if(!st[j])
{
st[j] = true;
q[tt++]=j;
}
}
}
}
return 1;
}
int main()
{
scanf("%d%d",&n,&k);
memset(h,-1,sizeof h);
while(k--)
{
int x,a,b;
scanf("%d%d%d",&x,&a,&b);
if(x==1)
{
add(a,b,0);
add(b,a,0);
}
else if(x==2)
{
add(a,b,1);
}
else if(x==3)
{
add(b,a,0);
}
else if(x==4)
{
add(b,a,1);
}
else
{
add(a,b,0);
}
}
for(int i=1;i<=n;i++)
add(0,i,1);
int t=spfa();
if(t==-1)
cout<<-1<<endl;
else
{
long long res=0;
for(int i=1;i<=n;i++)
res +=dist[i];
cout<<res<<endl;
}
return 0;
}
题2：区间
解题思路：这题我们把所有dist看成前缀和，然后就很好办了，最后答案是所有区域内的答案。
#include<iostream>
#include<cstring>
using namespace std;
const int N=50010,M=4*N;
int q[N],h[N],idx,e[M],ne[M],w[M];
bool st[N];
int dist[N];
int cnt[N];
int n;
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa()
{
int tt=0,hh=0;
memset(dist,-0x3f,sizeof dist);
dist[0]=0;
st[0]=true;
q[tt++]=0;
while(tt!=hh)
{
int t=q[hh++];
st[t]=false;
if(hh==N) hh=0;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(dist[j]<dist[t]+w[i])
{
dist[j] = dist[t]+w[i];
if(!st[j])
{
st[j]=true;
q[tt++]=j;
if(tt==N) tt=0;
}
}
}
}
}
int main()
{
cin >> n;
memset(h,-1,sizeof h);
for(int i=0;i<n;i++)
{
int a,b,c;
cin >>a>>b>>c;
add(a-1,b,c);
}
for(int i=1;i<=50001;i++)
add(i-1,i,0);
for(int i=1;i<=50001;i++)
add(i,i-1,-1);
spfa();
cout<<dist[50001]<<endl;
}
题3：1170. 排队布局
解题思路：这题我们把求的是最短路，如果有负环就输出-1，我们dist记录的是每头牛到万能源点0的距离，由于是求的是相对差，我们不妨把dist1变为0，先spfa一遍从万能源点0开始看看有没有负环，然后再spfa从1开始如果dist最后是0x3f3f3f3f那么就是无限长，否则输出distn就行了。
#include<iostream>
#include<cstring>
using namespace std;
const int N =1010 , M = 30010;
bool st[N];
int dist[N];
int q[N];
int h[N],idx,e[M],ne[M],w[M];
int cnt[N];
int n;
int ml,md;
void add(int a,int b,int c)
{
e[idx] =b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(int size)
{
memset(st,0,sizeof st);
memset(cnt,0,sizeof cnt);
memset(dist,0x3f,sizeof dist);
int tt=0,hh=0;
for(int i=1;i<=size;i++)
q[tt++] = i,st[i]=true;
dist[1] = 0;
while(hh!=tt)
{
int t=q[hh++];
if(hh==N) hh=0;
st[t]=false;
for(int i=h[t];~i;i=ne[i])
{
int j=e[i];
if(dist[j]>dist[t]+w[i])
{
dist[j] =dist[t] +w[i];
cnt[j] = cnt[t] +1;
if(cnt[j]>=n+1) return true;
if(!st[j])
{
st[j]=true;
q[tt++]=j;
if(tt==N) tt=0;
}
}
}
}
return false;
}
int main()
{
cin >> n >> ml >> md;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
add(i,i-1,0);
while(ml--)
{
int a,b;
int D;
cin >> a >> b >> D;
if(b<a)
swap(a,b);
add(a,b,D);
}
while(md--)
{
int a,b;
int D;
cin >> a >> b >> D;
if(b<a)
swap(a,b);
add(b,a,-D);
}
if(spfa(n))
cout<<-1<<endl;
else
{
spfa(1);
if(dist[n]==0x3f3f3f3f)
cout<<-2<<endl;
else
{
cout<<dist[n]<<endl;
}
}
return 0;
}
题目4：393. 雇佣收银员
解题报告：这题的dist代表前i个小时总共雇了多少个员工，由于不知道dist24，那么我们可以枚举他的大小，从0到总人数，只需要看i执行到什么时候最长路不存在正环就输出i。
#include<iostream>
#include<cstring>
using namespace std;
const int N =24 , M =100;
int h[N],idx , ne[M],e[M],w[M];
int dist[N];
int num[N];
bool st[N];
int r[N];
int T;
int q[N];
int cnt[N];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void build(int size)
{
for(int i=1;i<=24;i++)
{
add(i-1,i,0);
add(i,i-1,-num[i]);
if(i<8)
add(i+16,i,r[i]-size);
else
{
add(i-8,i,r[i]);
}
}
}
bool spfa(int size)
{
memset(cnt,0,sizeof cnt);
memset(st,0,sizeof st);
memset(dist,-0x3f,sizeof dist);
memset(h,-1,sizeof h);
idx = 0 ;
build(size);
int hh =0 ,tt=0;
q[tt++]=0;
dist[0] =0;
while(tt!=hh)
{
int t = q[hh++];
st[t]=false;
if(hh==N) hh=0;
for(int i=h[t];~i;i=ne[i])
{
int j = e[i];
if(dist[j]<dist[t]+w[i])
{
dist[j] = dist[t] +w[i];
cnt[j ] = cnt[t ] +1;
if(cnt[j]>=25) return false;//0也算在其中
if(!st[j])
{
st[j] =true;
q[tt++]=j;
if(tt==N) tt=0;
}
}
}
}
return true;
}
int main()
{
int t;
cin >> t;
while(t--)
{
memset(num,0,sizeof num);
for(int i=1;i<=24;i++)
cin >> r[i];
int n;
cin >> n;
for(int i=0;i<n;i++)
{
int x;
cin >> x;
num[x+1]++;
}
bool flag=0;
for(int i =0;i<=1000;i++)
{
if(spfa(i))
{
flag =true;
cout<<i<<endl;
break;
}
}
if(!flag)
cout<<"No Solution"<<endl;
}
return 0;
}
京公网安备 11010502036488号