NC20284. [SCOI2011]糖果
描述
输入描述
输入的第一行是两个整数N，K。
接下来K行，表示这些点需要满足的关系，每行3个数字，X，A，B。
如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；
如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；
如果X=3， 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；
如果X=4， 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；
如果X=5， 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；
输出描述
输出一行，表示lxhgww老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出-1。
示例1
输入:
5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1
输出:
11
C++11(clang++ 3.9) 解法, 执行用时: 31ms, 内存消耗: 4036K, 提交时间: 2020-10-05 16:18:35
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e5+5,M=5e5+5;
struct Edge{int to,w,nxt;}e[M];
int n,m,fst[N],tote,dis[N],cnt[N];
bool inq[N];LL ans;
queue<int>q;
void adde(int u,int v,int w){
if(w&&u==v){puts("-1");exit(0);}
e[++tote]=(Edge){v,w,fst[u]};fst[u]=tote;
}
int main(){
scanf("%d%d",&n,&m);
while(m--){
int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
if(opt==1)adde(x,y,0),adde(y,x,0);
if(opt==2)adde(x,y,1);
if(opt==3)adde(y,x,0);
if(opt==4)adde(y,x,1);
if(opt==5)adde(x,y,0);
}
for(int i=1;i<=n;i++)dis[i]=1,inq[i]=true,q.push(i);
while(!q.empty()){
int u=q.front();q.pop();inq[u]=false;
for(int i=fst[u],v,w;i;i=e[i].nxt){
v=e[i].to;w=e[i].w;
if(dis[v]<dis[u]+w){
dis[v]=dis[u]+w;cnt[v]=cnt[u]+1;
if(cnt[v]>=n){puts("-1");return 0;}
if(!inq[v])q.push(v),inq[v]=true;
}
}
}
for(int i=1;i<=n;i++)ans+=(LL)dis[i];
printf("%lld\n",ans);
return 0;
}