Description

幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

Input

输入的第一行是两个整数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个小朋友分到的糖果;

Output

输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出-1。

Sample Input

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

Sample Output

11

HINT

【数据范围】

对于30%的数据,保证 N<=100
对于100%的数据,保证 N<=100000
对于所有的数据,保证 K<=100000,1<=X<=5,1<=A, B<=N


Solution

差分约束模板题。

一样多就向自己连边,记得开long long。

Code

/*Program from Luvwgyx*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=3e5+10;
struct node{int to,nxt,w;}e[maxn<<1];
int n,K,tot,head[maxn],dis[maxn],cnt[maxn];bool vis[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
void add(int u,int v,int w){e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;}
queue<int >q;
bool spfa(){
    while(!q.empty()){
        int x=q.front();q.pop();vis[x]=0;
        for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
            if(dis[v]<dis[x]+e[i].w){
                dis[v]=dis[x]+e[i].w;cnt[v]++;
                if(cnt[v]>n)return 0;
                if(!vis[v]){q.push(v);vis[v]=1;}
            }
    }return 1;
}
signed main(){
    n=read();K=read();
    for(int i=1;i<=K;i++){
        int opt=read(),x=read(),y=read();
        if(opt==1)add(x,y,0),add(y,x,0);
        if(opt==2){if(x==y){puts("-1");return 0;}add(x,y,1);}
        if(opt==3)add(y,x,0);
        if(opt==4){if(x==y){puts("-1");return 0;}add(y,x,1);}
        if(opt==5)add(x,y,0);
    }for(int i=1;i<=n;i++)dis[i]=1,vis[i]=1,cnt[i]=1,q.push(i);
    if(!spfa()){puts("-1");return 0;}int ans=0;
    for(int i=1;i<=n;i++)ans+=dis[i];write(ans);
    return 0;
}

发表评论