Acwing1169.糖果（差分约束最小值判断是否有解

添加链接描述

#include
using namespace std;
const int N&＃61;1e5&＃43;10,M&＃61;3e5&＃43;10;
int n,k;
int h[N],w[M],e[M],ne[M],idx;
typedef long long ll;
void add(int a,int b,int c){w[idx]&＃61;c;e[idx]&＃61;b,ne[idx]&＃61;h[a],h[a]&＃61;idx&＃43;&＃43;;
}
int vis[N],dist[N],cnt[N];
bool spfa(){memset(dist,-0x3f,sizeof dist);stack<int>q;//会Tleq.push(0);vis[0]&＃61;1;dist[0]&＃61;0;while(q.size()){int p&＃61;q.top();q.pop();vis[p]&＃61;0;for(int i&＃61;h[p];~i;i&＃61;ne[i]){int j&＃61;e[i];if(dist[j]<dist[p]&＃43;w[i]){dist[j]&＃61;dist[p]&＃43;w[i];cnt[j]&＃61;cnt[p]&＃43;1;if(cnt[j]>&＃61;n&＃43;1)return 0;if(!vis[j]){vis[j]&＃61;1;q.push(j);}}}}return 1;
}
int main(){scanf("%d%d",&n,&k);memset(h,-1,sizeof h);for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;){int a,b,x;scanf("%d%d%d",&x,&a,&b);if(x&＃61;&＃61;1)add(a,b,0),add(b,a,0);else if(x&＃61;&＃61;2)add(a,b,1);else if(x&＃61;&＃61;3)add(b,a,0);else if(x&＃61;&＃61;4)add(b,a,1);else if(x&＃61;&＃61;5)add(a,b,0);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){add(0,i,1);//每个人至少要有一个糖果}if(!spfa())puts("-1");else {ll res&＃61;0;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)res&＃43;&＃61;dist[i];printf("%lld\n",res);}return 0;
}