P3275 [SCOI2011]糖果
差分约束模板题，基本思路就是$d[v]+w[v,u]<=d[u]$，$Spfa$更新方法，
有点套路的是要建立原点，即图中不存在的点来向每个点加边，但同样这是必须的，因为这样做是有意义的，每个小朋友必须要有一颗糖果
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue> #define N 10000000
using namespace std; int n,k,tot,head[N];
long long ans;
struct node{
int to,next,w;
}e[N]; void add(int u,int v,int w){
e[++tot].to=v,e[tot].next=head[u],head[u]=tot,e[tot].w=w;
} int d[N],in[N]; struct npdE{
int to,dis;
bool operator < (npdE x)const{
return dis>x.dis;
}
};
queue<npdE>Q;
bool vis[N]; void spfa(){
Q.push((npdE){,});
vis[]=;
while(!Q.empty()){
int u=Q.front().to;vis[u]=,Q.pop();
if(in[u]>n) {
printf("-1");return;
}
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(d[v]<d[u]+e[i].w){
d[v]=d[u]+e[i].w;
if(!vis[v]) in[v]=in[u]+,vis[v]=,Q.push((npdE){v,d[v]});
}
}
}
for(int i=;i<=n;i++) ans+=d[i];
printf("%lld\n",ans);
} int main()
{
scanf("%d%d",&n,&k);
for(int x,u,v,i=;i<=k;i++){
scanf("%d%d%d",&x,&u,&v);
if(x==) add(u,v,),add(v,u,);
else if(x==) add(u,v,);
else if(x==) add(v,u,);
else if(x==) add(v,u,);
else add(u,v,);
if(x==||x==) if(u==v) {return puts("-1"),;}
}
for(int i=n;i>=;i--) add(,i,);
spfa();
return ;
}