BZOJ2330/洛谷P3275（糖果）

阳光穿透心脏的1/2处 2021-11-17 23:58 239阅读 0赞

## 题意： ##

## 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

## 分析：很巧妙的一道题，利用边权只有0和1的特点，转化为了强连通分量问题来处理最长路，详见《算法竞赛进阶指南》P417。 ##

## 代码： ##

#include <queue>
    #include <cstdio>
    #include <vector>
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    #define ll long long
    using namespace std;
    const int N = 100006;
    int n, m, num, top, cnt;
    int d[N], dfn[N], low[N], st[N], c[N], deg[N], f[N], scc[N];
    bool ins[N];
    vector<pair<int, int> > e[N], ec[N];
    queue<int> q;
    
    inline void add(int x, int y, int z) {
    	e[x].push_back(make_pair(y, z));
    }
    
    inline void addc(int x, int y, int z) {
    	ec[x].push_back(make_pair(y, z));
    	++deg[y];
    }
    
    void tarjan(int x) {
    	dfn[x] = low[x] = ++num;
    	st[++top] = x;
    	ins[x] = 1;
    	for (unsigned int i = 0; i < e[x].size(); i++) {
    		int y = e[x][i].first;
    		if (!dfn[y]) {
    			tarjan(y);
    			low[x] = min(low[x], low[y]);
    		} else if (ins[y])
    			low[x] = min(low[x], dfn[y]);
    	}
    	if (dfn[x] == low[x]) {
    		++cnt;
    		int y;
    		do {
    			y = st[top--];
    			ins[y] = 0;
    			c[y] = cnt;
    			++scc[cnt];
    		} while (y != x);
    	}
    }
    
    int main() {
    	cin >> n >> m;
    	for (int i = 1; i <= m; i++) {
    		int o, a, b;
    		scanf("%d %d %d", &o, &a, &b);
    		if (o == 2) add(a, b, 1);
    		else if (o == 3) add(b, a, 0);
    		else if (o == 4) add(b, a, 1);
    		else if (o == 5) add(a, b, 0);
    		else {
    			add(a, b, 0);
    			add(b, a, 0);
    		}
    	}
    	for (int i = 1; i <= n; i++) add(0, i, 1);
    	tarjan(0);
    	for (int x = 0; x <= n; x++)
    		for (unsigned int i = 0; i < e[x].size(); i++) {
    			int y = e[x][i].first, z = e[x][i].second;
    			if (c[x] == c[y]) {
    				if (!z) continue;
    				puts("-1");
    				return 0;
    			}
    			addc(c[x], c[y], z);
    		}
    	for (int i = 1; i <= cnt; i++)
    		if (!deg[i]) q.push(i);
    	while (q.size()) {
    		int x = q.front();
    		q.pop();
    		for (unsigned int i = 0; i < ec[x].size(); i++) {
    			int y = ec[x][i].first, z = ec[x][i].second;
    			f[y] = max(f[y], f[x] + z);
    			if (!--deg[y]) q.push(y);
    		}
    	}
    	ll ans = 0;
    	for (int i = 1; i <= cnt; i++) ans += (ll)f[i] * scc[i];
    	cout << ans << endl;
    	return 0;
    }