一道条件非常多的差分约束
把\( a < b \)转化为\( a-b \le -1\)就可做了
\( a>b \)的情况同理
若有负环则无解输出-1
注意本题中要求每个人都有糖果
所以假设一个源点\( d_{0} \)，使\( d_{i}-d_{0} \ge 1 \ , \ (1 \le i \le n) \)
另外，本题要求得是最小值
\( x_{i}-x_{j} \le a_{k} \)的形式求出的是最大值
要转化成 \( x_{j}-x_{i} \ge a_{k} \)的形式求解最小值
每个人的最小值即为\( dis_{i} \)，所以求和
因为和是负数，所以输出-ans
ans会爆int
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = ;
const int MAXM = ;
int cnt=,u[MAXM],v[MAXM],w[MAXM],first[MAXN],next[MAXM];
bool vis[MAXN];
int inq[MAXN],dis[MAXN],f[MAXN];
int n,k;
void addedge(int ux,int vx,int wx){
++cnt;
u[cnt]=ux;
v[cnt]=vx;
w[cnt]=wx;
next[cnt]=first[ux];
first[ux]=cnt;
}
bool spfa(int s){
queue<int> q;
for(int i=;i<=n;i++)
dis[i]=0x3f3f3f3f;
q.push(s);
dis[s]=;
inq[s]=;
vis[s]=;
f[s]=;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=;
f[u]=;
for(int i=first[u];i;i=next[i]){
if(w[i]+dis[u]<dis[v[i]]){
dis[v[i]]=w[i]+dis[u];
if(!vis[v[i]]){
vis[v[i]]=;
inq[v[i]]++;
q.push(v[i]);
if(inq[v[i]]>=n)
return false;
}
}
}
}
return true;
}
int main(){
scanf("%d %d",&n,&k);
int x,a,b;
for(int i=;i<=k;i++){
scanf("%d",&x);
if(x==){
scanf("%d %d",&a,&b);
addedge(a,b,);
addedge(b,a,);
}
else if(x==){
scanf("%d %d",&a,&b);
addedge(a,b,-);
if(a==b){
printf("-1");
return ;
}
}
else if(x==){
scanf("%d %d",&a,&b);
addedge(b,a,);
}
else if(x==){
scanf("%d %d",&a,&b);
addedge(b,a,-);
if(a==b){
printf("-1");
return ;
}
}
else{
scanf("%d %d",&a,&b);
addedge(a,b,);
}
}
for(int i=n;i>=;i--)
addedge(,i,-);
if(!spfa()){
printf("-1");
return ;
}
long long ans=;
for(int i=;i<=n;i++)
ans+=-dis[i];
printf("%lld",ans);
return ;
}