当前位置:首页 > 差分约束 > 正文
BZOJ1077[SCOI2008]天平
3397+

题目大意:n个砝码,知道他们都是1、2、3克的,以及部分他们之间的大小关系,请问再选2个砝码,比a和b重、轻、一样重的情况各有多少种?

Description

  你有n个砝码,均为1克,2克或者3克。你并不清楚每个砝码的重量,但你知道其中一些砝码重量的大小关系。
你把其中两个砝码A和B放在天平的左边,需要另外选出两个砝码放在天平的右边。问:有多少种选法使得天平的左
边重(c1)、一样重(c2)、右边重(c3)?(只有结果保证惟一的选法才统计在内)

Input

  第一行包含三个正整数n,A,B(1<=A,B<=N,A和B不相等)。砝码编号为1~N。以下n行包含重量关系矩阵,
其中第i行第j个字符为加号“+”表示砝码i比砝码j重,减号“-”表示砝码i比砝码j轻,等号“=”表示砝码i和砝
码j一样重,问号“?”表示二者的关系未知。存在一种情况符合该矩阵

Output

  仅一行,包含三个整数,即c1,c2和c3。

Sample Input

6 2 5
?+????
-?+???
?-????
????+?
???-?+
????-?

Sample Output

1 4 1

HINT

【数据规模】 4<=n<=50

解题思路

现在只知道谁比谁重、谁比谁轻、谁和谁一样重,如何比较2个2个之间的关系呢?一种思路是求出每个砝码的取值范围,默认是[1,3],如果出现a比c重、b比d重,那么a、b的范围就是[2,3],c、d的范围就少[1,2],如何确定a+b比c+d重呢?由传递性可知,a+b很明显比c+d重,但是实际上比较到时候,我们更多会是用a+b的最小值跟c+d的最大值去比较,这样才是最保险、最确定的关系,结果a和b都取最小值2、c和d都取最大值2,a+b可能等于c+d,即认为a+b不一定比c+d重。虽然是不可能,但比较时没想那么多或者很难解决这种问题。因此,确定某个砝码的取值范围再比较是不妥的。

另外一种方法就是利用差分约束,a比c重,那么a-c的范围就是[1,2],这样就不会出现a取最小值时,c取了不该取的最大值。a-c>=1而且a-c<=2,大于等于转成最长路,小于等于转成最短路,就这样可以求出任意两个砝码之间的差的范围。n比较小,用Floyd就行,以最长路为例:如果i-k>=a,k-j>=b,那么i-j>=a+b,原理i-j的距离跟a+b取最大值,这样约束条件才同时满足。

最后怎么判断两个砝码与两个砝码的大小关系?以a+b>i+j为例,那么a-i>j-b就行了,如果a-i的最小值比j-b的最大值要大,那就一定满足条件(无论a,b,i,j怎么取值);当然,a-j>i-b也是可以的,两种情况是或者的关系。对于a+b<i+j道理是一样的,只是相等的判断比较麻烦。相等的时候,a+b==i+j也即a-i==b-j,此时a-i和b-j各有一个范围,范围一样还不行,还要取值必须一样才一定满足条件,故需要a-i和b-j的最大最小值全都一样!对于另外一种变形也是一样的判断一下。

已知砝码a和b,另外两个暴力枚举就行,因为n只有50!如果满足条件,对于的计数变量加价即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

BZOJ1077[SCOI2008]天平:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!