这题我自我感觉特恶心

因为就是这么一道题我听取WA声一片

不信找洛谷 L_Y_T P3275 的做题记录……

好了，废话少说，步入正题。

 

题目描述

幼儿园里有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。

 

输入输出样例

输入样例#1： 

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

输出样例#1： 

11

这道题有五种操作

如果X=1， 表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多；如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果；如果X=3， 表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果；如果X=4， 表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果；如果X=5， 表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果；

这样的话，我们就可以对其进行分析

首先，

如果 x == 1 的话 ， 就是A和B的糖果相等

换言之，就是 A == B ，即 A-B < 0 , B-A < 0 ;

换到程序代码上就是 add(a,b,0) ; add(b,a,0) ;

如果 x == 2 的话 , 表示A 的 必须少于B 的. 因为题目要求是求最少要准备的糖果数量,并且A还必须小于B .所以,不难想出,A< B .即A-B < 1 ;即add(a,b,1);

如果 x == 4 的话 , 就和上面讲的一样了!

如果 x == 3 , 那么A的必须不少于B的.让我们试想一下,如果A比B多的话,那么,我们恒可能又要多准备糖果,所以,当A <= B , A-B <

 0 时最少;add(A,B,0) ;

如果 x == 5 ,情况相同 .

然后就可以开开心心的看代码了!!

主程序

int main(){
	cin >> n >> k ;
	int u , v , opt ;
	for(int i = 1 ; i<= k ; i ++){
		cin >> opt >> u >> v ;
		if(opt == 1) add(u , v , 0) , add(v , u , 0) ;
		else if(opt == 2){
			if(u == v) {
				cout << -1 ;
				return 0 ;
			}add(u,v,1) ;
		}
		else if(opt == 3) add(v,u,0) ;
		else if(opt == 4) {
			if(u == v){
				cout << -1 ;
				return 0 ;
			}add(v,u,1) ;
		}
		else if(opt == 5){
			add(u,v,0) ;
		}
	}

   //我们要从0开始
	for(int i = n ; i >= 1 ; i --) add(0,i,1) ;
	vis[0] = 1 ;

下面是SPFA的函数

//因为我们并没有定义负值,所以我们可以开开心心的用队列版spfa
vis[0] = 1 ;
	q.push(0) ;
	while(!q.empty()){
		int u = q.front() ;
		q.pop() ;
		vis[u] = 0 ;
		if(tot[u] == n-1) {
			cout << -1 ;
			return 0 ;
		}tot[u] ++ ;
		for(int i = head[u] ; i ; i = a[i].next){
			int v = a[i].to ;
			if(dis[v] < dis[u] + a[i].w){
				dis[v] = dis[u] + a[i].w ;
				if(!vis[v]){
					vis[v] = 1 ;
					q.push(v) ;
				}
			}
		}
	}

 

in the end , 开开心心的输出

long long ans = 0 ;
	for(int i = 1 ; i <= n ; i ++){
		ans += dis[i] ;
	}
	cout << ans ;
	return 0 ; //这是个好习惯

开开心心的结束喽!!!

算了,还是补个全代码吧!

#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
#include<algorithm>
#define maxn 300000 
using namespace std ;
int n , m , head[maxn] , vis[maxn] , dis[maxn] ;
struct dy{
	int from , to , w , next ;
}a[maxn];
queue<int>q ;
int t ;
void add(int x , int y , int z){
	a[++t].from = x ;
	a[t].to = y ;
	a[t].w = z ;
	a[t].next = head[x] ;
	head[x] = t ;
}int tot [maxn] ;
int k ;
void spfa(){
	vis[0] = 1 ;
	q.push(0) ;
	while(!q.empty()){
		int u = q.front() ;
		q.pop() ;
		vis[u] = 0 ;
		if(tot[u] == n-1) {
			cout << -1 ;
			exit(0) ;
		}tot[u] ++ ;
		for(int i = head[u] ; i ; i = a[i].next){
			int v = a[i].to ;
			if(dis[v] < dis[u] + a[i].w){
				dis[v] = dis[u] + a[i].w ;
				if(!vis[v]){
					vis[v] = 1 ;
					q.push(v) ;
				}
			}
		}
	}
}
int main(){
	cin >> n >> k ;
	int u , v , opt ;
	for(int i = 1 ; i<= k ; i ++){
		cin >> opt >> u >> v ;
		if(opt == 1) add(u , v , 0) , add(v , u , 0) ;
		else if(opt == 2){
			if(u == v) {
				cout << -1 ;
				return 0 ;
			}add(u,v,1) ;
		}
		else if(opt == 3) add(v,u,0) ;
		else if(opt == 4) {
			if(u == v){
				cout << -1 ;
				return 0 ;
			}add(v,u,1) ;
		}
		else if(opt == 5){
			add(u,v,0) ;
		}
	}
	for(int i = n ; i >= 1 ; i --) add(0,i,1) ;
	spfa() ;
	long long ans = 0 ;
	for(int i = 1 ; i <= n ; i ++){
		ans += dis[i] ;
	}
	cout << ans ;
	return 0 ;
}

真的结束

TRUE ENDING