bzoj2330 糖果

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

HINT

【数据范围】

对于30%的数据，保证 N<=100

对于100%的数据，保证 N<=100000

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

/*

差分约束运用了最短路中的三角形不等式，即d[v]<=d[u]+w(u, v)，当然，最长路的话变形就行了，即d[v]>=d[u]+w(u, v)。

我们根据本题给的约束可以构造这样的不等式（因为最短路的话是负数，很不好判断，如果化成最长路，就都是正数了）：

首先所有的人都满足，d[i]>=1

按照输入a和b

d[a]==d[b]，有 d[a]-d[b]>=0, d[b]-d[a]>=0

d[a]<d[b]，有 d[b]-d[a]>=1

d[a]>=d[b]，有 d[a]-d[b]>=0

d[a]>d[b]，有 d[a]-d[b]>=1

d[a]<=d[b]，有 d[b]-d[a]>=0

然后建图就行。（在这里，不要添加附加源，如果非要加的话逆着添加，因为此题数据可能造了个很大的正环。。

*/

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }

inline const int getint() { int r=, k=; char c=getchar(); for(; c<''||c>''; c=getchar()) if(c=='-') k=-; for(; c>=''&&c<=''; c=getchar()) r=r*+c-''; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=;

int ihead[N], n, m, vis[N], tm[N], cnt, q[N], front, tail;

long long d[N];

struct ED { int to, next, w; } e[];

inline void add(const int &u, const int &v, const int &w) {

    e[++cnt].next=ihead[u]; ihead[u]=cnt; e[cnt].to=v; e[cnt].w=w;

}

const bool spfa() {

    for1(i, , n) q[i]=i, d[i]=, vis[i]=, tm[i]=;

    front=; tail=n+;

    int u, v;

    while(front!=tail) {

        u=q[front++]; if(front==N) front=; vis[u]=;

        for(int i=ihead[u]; i; i=e[i].next) if(d[v=e[i].to]<d[u]+e[i].w) {

            d[v]=d[u]+e[i].w;

            if(++tm[v]>=n) return ; //环的点数>=n，每个点最多更新n-1次。

            if(!vis[v]) {

                vis[v]=; q[tail++]=v;

                if(tail==N) tail=;

            }

        }

    }

    return ;

}

int main() {

    read(n); read(m);

    int u, v, x;

    for1(i, , m) {

        read(x); read(u); read(v);

        if(x==) add(u, v, ), add(v, u, );

        else if(x==) {

            if(u==v) { puts("-1"); return ; }

            add(u, v, );

        }

        else if(x==) add(v, u, );

        else if(x==) {

            if(u==v) { puts("-1"); return ; }

            add(v, u, );

        }

        else add(u, v, );

    }

    if(spfa()) {

        long long ans=;

        for1(i, , n) ans+=d[i];

        printf("%lld", ans);

    }

    else puts("-1");

    return ;

}

//自己写的

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<algorithm>

#include<queue>

#define ll long long

using namespace std;

const int maxn = ;

struct edge{

    int v;

    int w;

    int nxt;

}e[maxn*];

int n,k;

int cnt,head[maxn];

int rd[maxn];

bool vis[maxn];

ll dis[maxn];

int read(){

    char ch=getchar();

    int f=,x=;

    while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};

    while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};

    return x*f;

}

int ins(int u,int v,int w){

    cnt++;

    e[cnt].v = v;

    e[cnt].w = w;

    e[cnt].nxt = head[u];

    head[u] = cnt;

}

bool spfa(){

    int now,nt;

    queue<int> q;

    for(int i = ;i <= n;i++){

        q.push(i);

        dis[i] = rd[i]=;

    }

    while(!q.empty()){

        now = q.front();

        q.pop();

        for(int i = head[now];i;i = e[i].nxt){

            nt = e[i].v;

            if(dis[nt]<dis[now]+e[i].w){

                dis[nt] = dis[now]+e[i].w;

                if(!vis[nt]){

                    vis[nt] = true;

                    q.push(nt);

                    rd[nt]++;

                    if(rd[nt]>n) return false;

                }

            }

        }

        vis[now] = false;

    }

    return true;

}

int main(){

    n = read();

    k = read();

    int x,a,b;

    for(int i = ;i <= k;i++){

        x = read();

        a = read();

        b = read();

        if(x == ){

            ins(a,b,);

            ins(b,a,);

        }else if(x == ){

            if(a==b){

                cout<<-;

                return ;

            }

            ins(a,b,);

        }else if(x == ){

            ins(b,a,);

        }else if(x == ){

            if(a==b){

                cout<<-;

                return ;

            }

            ins(b,a,);

        }else{

            ins(a,b,);

        }

    }

    ll ans = ;

    if(spfa()){

        for(int i = ;i <= n;i++) ans += dis[i];

        cout<<ans;

    }else{

        cout<<-;

    }

    return ;

}

巴特西