rockdu
题目描述
幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
输入输出格式
输入格式：
输入的第一行是两个整数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。
输入输出样例
说明
【数据范围】
对于30%的数据，保证 N<=100
对于100%的数据，保证 N<=100000
对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N
很好的差分约束板子题，可以复习用。对于这样的不等式，我们对它构建最短路（或最长路）模型加以验证，这就是差分约束，有篇博客讲的很好，包括前置技能都十分详细：“有篇博客”。(垃圾出题人，第六个点要想不TLE居然要反向加超级原点的边……!#%$%$@#$@)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define LL long long
#define ORG 0
#define FIN (n + 1)
using namespace std;
const int maxn = 4e5 + 5;
const int maxm = 4e5 + 5;
struct edge {
int v, w, next;
}e[maxn];
int cnt, head[maxn], dis[maxn], times[maxn];
int n, m;
bool vis[maxn];
void adde(const int &u, const int &v, const int &w) {
e[++cnt] = (edge) {v, w, head[u]};
head[u] = cnt;
}
bool SPFA(int u) {
vis[u] = 0;
for(register int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if(dis[u] + e[i].w < dis[v]) {
dis[v] = dis[u] + e[i].w;
if(vis[v]) continue;
if(times[v] > n - 2) return 0;
times[v] += vis[v] = 1;
if(!SPFA(v)) return 0;
}
}
return 1;
}
int main() {
scanf("%d%d", &n, &m);
int u, v, o;
for(register int i = n; i >= 1; --i)
adde(ORG, i, 0);
for(register int i = 1; i <= m; ++i) {
scanf("%d%d%d", &o, &u, &v);
if(o == 1) adde(u, v, 0), adde(v, u, 0);
else if(o == 2) adde(u, v, -1);
else if(o == 3) adde(v, u, 0);
else if(o == 4) adde(v, u, -1);
else if(o == 5) adde(u, v, 0);
else if((o == 2 || o == 4) && u == v) {
putchar('-'), putchar('1');
return 0;
}
}
dis[ORG] = -1;
if(!SPFA(ORG)) {
printf("%d", -1);
return 0;
}
LL ans = 0;
for(register int i = 1; i <= n; ++i)
ans += dis[i];
printf("%lld", -ans);
return 0;
}
没有帐号? 立即注册