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

若不懂差分约束先看布局

若问题是像本题一样一个点到各个点距离最小

同样可以将题目中的条件写成如下形式

xj−xi≤D        //两个点距离小于D
xj−xi≥D        //两个点距离大于D

我们对于第一个不等式作如下转化

    xj − xi ≤ D        
=> xj ≤ xi + D 

发现它和最长路问题中的三角不等式是一致的:

//D是S到V的最短路 C是U到V的边权
D(s,v)≥D(s,u)+C(u,v),(u,v)∈E

于是我们可以将

xj - D ≤ xi 这个不等式转化为
由j到i的一条长度为-D的边
xj ≥ xi + D 这个不等式转化为
由i到j的一条长度为D的边

详细证明请看:chrt
然后由1作为起点跑SPFA(必须为SPFA因为dij在有负边的时候不能使用)
对于题目:若有负权环则输出-1,否则直接输出1~N的距离即可
判断负环
有一种较优秀的方法:对于每一个点记录从起点到这个点最长路径包含的边的条数。
若边的条数大于N,易证这个图有负环。
代码

#include <iostream>
#include <cstdio>
#include <queue>

const long long MAXN = 200005,MAXX = 400005,INF = 10e8;

using namespace std;

long long N,K,e = 1,ans,d[MAXX],sum[MAXX],head[MAXX];
bool inq[MAXX];

struct node{
    long long v,c,next;
}edge[MAXX];

queue<long long>q;

inline void addedge(long long u,long long v,long long c){
    edge[e] = (node){v,c,head[u]};head[u] = e++;
}

inline long long read(){
    long long x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch) {ch = getchar();}
    while('0' <=ch&&ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
    return x;
} 

inline bool init()
{
    N = read();K = read();
    
    long long u,v,x;
    
    for(long long i = 1;i <= K;i++)
    {
        x = read();u = read();v = read();
        
        if(x == 1) {addedge(u,v,0);addedge(v,u,0);continue; }
        
        if(x == 2) {if(u == v) return false; addedge(u,v,1);continue;}
        
        if(x == 3) {addedge(v,u,0);continue;}
        
        if(x == 4) {if(u == v) return false;addedge(v,u,1);continue;}
        
        if(x == 5) {addedge(u,v,0);continue;}
    }

    for(long long i = N;i >= 1;i--) addedge(0,i,1);
    return true;
}

inline bool spfa(){
    
    q.push(0);inq[0] = true;sum[0] = 1;
    
    while(!q.empty()){
        int u = q.front();q.pop();inq[u] = false;
        for(long long i = head[u];i;i = edge[i].next){
            long long v = edge[i].v,c = edge[i].c;
            
            if(d[v] < d[u] + c){
                d[v] = d[u] + c;
                sum[v] = sum[u] + 1;
                
                if(sum[v] > N + 1) return false;
                
                if(!inq[v]){q.push(v);inq[v] = true;}
            }
        }
    }
    return true;
}

int main()
{
    if(!init()) {printf("-1");return 0;}
    if(!spfa()) {printf("-1");return 0;}
    
    for(long long i = 1;i <= N;i++) ans += d[i];
    
    printf("%lld",ans);
    return 0;
} 
Last modification:October 1st, 2018 at 08:21 am
If you think my article is useful to you, please feel free to appreciate