2021.07.23 P3275 糖果（差分约束）
[P3275 SCOI2011]糖果 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
重点：
1.为了满足更多更多约束条件，合适地选择最长路或最短路（我个憨憨，强行最短路，因此还加了负号）
题意：
k个约束条件，求满足所有约束条件并且每个点的值都大于0的每个点点权之和的最小值。
分析：
v(A,B)为从A到B的边权的值，且A点点权小于B。为了让点权之和最小，强行要求A>=B||A<=B为A==B。为了满足更多约束条件，跑最长路，记得加超级源点。
当x1时，v(A,B)=v(B,A)=0;当x2时，v(A,B)=1;当x3时，v(B,A)=0;当x4时，v(B,A)=1;当x==5时，v(A,B)=0。
代码如下：
//为了满足更多的约束条件，一定要跑最长路！！！
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const ll inf=1e18;
int n,m,cnt,head[N],vis[N],tot[N];
ll dis[N];
struct node{
int to,next,val;
}a[N];
struct nodei{
int pos;
ll dis;
bool operator <(const nodei &b)const{
return dis<b.dis;
}
};
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')w=-1;
ch=getchar();
}
while(ch<='9'&&ch>='0'){
s=s*10+ch-'0';
ch=getchar();
}
return s*w;
}
void add(int u,int v,int w){
++cnt;
a[cnt].to=v;
a[cnt].next=head[u];
a[cnt].val=w;
head[u]=cnt;
}
int spfa(int s){
//memset(dis,-1,sizeof(dis));
priority_queue<nodei>q;
q.push({s,0});
vis[s]=tot[s]=1;
dis[s]=0;
while(!q.empty()){
nodei tmp=q.top();q.pop();
int x=tmp.pos;
vis[x]=0;
++tot[x];
if(tot[x]==n)return 0;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(dis[v]<dis[x]+a[i].val){
dis[v]=dis[x]+a[i].val;
if(!vis[v]){
vis[v]=1;
q.push({v,dis[v]});
}
}
}
}
return 1;
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
int op,u,v;
op=read();u=read();v=read();
if(op==1)add(u,v,0),add(v,u,0);
else if(op==2){
if(u==v)return cout<<"-1",0;
add(u,v,1);
}else if(op==3)add(v,u,0);
else if(op==4){
if(u==v)return cout<<"-1",0;
add(v,u,1);
}else if(op==5)add(u,v,0);
}
for(int i=1;i<=n;i++)add(n+1,i,1);
if(!spfa(n+1))return cout<<"-1",0;
ll ans=0;
for(int i=1;i<=n;i++)ans+=dis[i];
cout<<ans;
return 0;
}
