bzoj2330(差分约束)

时间:2022-07-11 15:10:57

题解:这道题是练差分约束的一道好题目吧,我具体在代码中注释,这样更加好理解,

为什么求最长路呢?因为这样保证了满足条件,如果存在正权环,就表示无解,就是

正权环之间不断要更多的糖果才行。

 #include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std; typedef long long ll;
const int N=; int s,dis[N],mark[N],n,m;
int cnt=,head[N],next[N*],rea[N*],val[N*];
bool vis[N]; void add(int u,int v,int fee)
{
cnt++;
next[cnt]=head[u];
head[u]=cnt;
rea[cnt]=v;
val[cnt]=fee;
}
bool spfa()
{
queue<int>q;
q.push();
vis[dis[]=]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i!=-;i=next[i])
{
int v=rea[i],fee=val[i];
if(dis[u]+fee>dis[v])
{
dis[v]=dis[u]+fee;
if(++mark[v]>=n) return ;//表示无法满足
if(!vis[v])
{
vis[v]=;
q.push(v);
}
}
}
vis[u]=;
}
return ;
}
int main()
{
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
int xh,u,v;
scanf("%d%d%d",&xh,&u,&v);
switch (xh)
{
case :if(u!=v) add(u,v,),add(v,u,);
break;
case :if(u==v)
{
printf("-1");
return ;
}
add(u,v,);break;
case :if(u!=v) add(v,u,);break;//表示可以到达
case :if(u==v)
{
printf("-1");
return ;
}
add(v,u,);break;//因为最少,所以只要多一格糖果就可以了。
case :if(u!=v) add(u,v,);break;
}
}
for(int i=n;i;i--)
add(,i,);//初始,开辟超源点。
if(!spfa()) printf("-1");
else
{
ll ans=;
for(int i=;i<=n;i++)
ans+=dis[i];
printf("%lld\n",ans);
}
}