网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
聪明的推销员
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | salenet.in | 输出文件 | salenet.out |
【题目描述】
某商品推销员到某小区推销产品,产品推销除了商品质量好之外,还需要客户能影响和带动身边信赖他的人也购买,如果A购买了产品,那么信赖A的B就有可能也购买,那么信赖B的C就也可能成为潜在客户,依据这种信赖关系,就可能构成一个庞大的潜在客户网。聪明的推销员经过细心调查整理了这个小区里N个人的信赖关系,并且用1~N给这N个人编号。另外,这N个人中有P个潜在客户可能会被推销员直接说服购买产品,细心的推销员还估算了说服每个人具体需要花费的时间,那么请你帮推销员计算一下他最少需要花费多长时间来建立起这N个人的潜在客户网?如果不能把这N个人全部纳入潜在客户网,输出不能被纳入网络的人的编号。注意,信赖关系不一定是相互的啊!
【输人格式】
输入文件第一行只有一个整数n(n<=3000)。
第二行是整数p。表示能被说服的人数,1≤p≤n。
接下来的p行,每行有两个整数,第一个数是一个能被说服的人的编号,第二个数表示他被说服需要花费的时间。这个数不超过20000个时间单位。
紧跟着一行只有一个整数r,1≤r≤8000。然后r行,每行两个正整数,表示数对(A, B),B信赖A。
【输出格式】
如果可以把N个人全部纳入潜在客户网,第一行输出YES,并在第二行输出所需要花费的最少说服时间。否则输出NO,并在第二行输出不能纳入网络的人编号中,编号最小的。
【输入样例】
Example1:
3
2
1 10
2 100
2
1 3
2 3
Example2:
4
2
1 100
4 200
2
1 2
3 4
【输出样例】
Example1:
YES
110
Example2:
NO
3
【数据规模】
对于30%的输入数据有n<=10。
对于100%的输入数据有n<=3000。