Poj 1018 Communication System

http://acm.pku.edu.cn/JudgeOnline/problem?id=1018
今天steve同学问了我这个题，很久以前做的题，使用了一个搜索加剪枝的做法： 首先B的值肯定是供应商的设备中的一个带宽值,所以你可以枚举所有的带宽
其次 对于每一个带宽 从供应商那选取一个满足条件的设备，并且价值是最小的 如果所有的供应商都能满足这个带宽 那么记录下B/P,然后和最大值比较 取最大值为 二者的最大
这样枚举到最后如果没有剪纸的话 我可以枚举到所有不是很差的设备 并且保证这个B/P的最大的
但是我们可以利用一些条件剪枝：如果有一个供应商无法满足这个带宽 那么更大的带宽就不需要枚举了，所以从小到大枚举所有的带宽，可以利用这个条件来剪枝。
以给的数据为例：
1 3
3 100 25 150 35 80 25
2 120 80 155 40
2 100 100 120 110
这样当B枚举到150的时候，即B=150,第三个供应商的所有设备都小于150，取任何一个设备都会导致B<150,矛盾。当然大于150的更不用枚举了，直接剪掉。
这道题主要是先固定住B的值，即依次枚举B的值，这样就会比较容易想了。

/**
 *Author fuliang <[e-mail]>
 * poj 1018 Communication System
 */
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Device{
	int b;
	int p;
};

vector< vector<Device> > devs;
vector<int> bands;
const int MIN_PRICE = 10000000;

void solve(){
	int i,j,k,v;
	int total;
	double max_pb = 0;
	int min;
	bool found;
	for(i = 0; i < bands.size(); i++){
		total = 0;
		for(j = 0; j < devs.size(); j++){
			min = MIN_PRICE;
			found = false;
			for(k = 0; k < devs[j].size(); k++){
				//find the min price device of all the band santified devices
				if(devs[j][k].b >= bands[i] && devs[j][k].p < min ){
					min = devs[j][k].p;
					found = true;
				}
			}

			if(found){//found, add the min price to the total,and consider the other devices
				total += min;
			}else{//not found the manufacturer in the device 
				break;
			}
		}
		//calculate the max of the min{bi} / sum(pi)
		if(found){
			double pb =  bands[i] * 1.0 / total;
			if(max_pb < pb)
				max_pb = pb;
		}else{
			break;//the more band width is not possible
		}
	}
	cout.setf(ios::fixed,ios::floatfield);
	cout.precision(3);
	cout << max_pb << endl;
}

int main(){
	int ncases;
    
	cin >> ncases;
	while(ncases--){
		int i,j,n,m;
		cin >> n;
		devs.clear();
		bands.clear();
		for(i = 0; i < n; i++){
			vector<Device> v;
			cin >> m;
			for(j = 0; j < m; j++){
				Device d;
				cin >> d.b >> d.p;
				v.push_back(d);
				bands.push_back(d.b);
			}
			devs.push_back(v);
		}
		sort(bands.begin(), bands.end());		
		solve();
	}
	return 0;
}

评论

2 楼 samwalt 2009-08-05  

谢谢，我忽略了一个小问题，修正了，也AC了。

1 楼 fuliang 2009-08-04  

这个题虽然ac了，但steve提醒还有一个问题。
应该枚举所有设备的band的时候，保证选中枚举的这个设备，后修改代码如下：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Device{
	int b;
	int p;
};

bool cmp(const Device &d1,const Device &d2){
	return d1.b < d2.b;
}

vector< vector<Device> > devs;
vector<Device> sorted_devs;
const int MIN_PRICE = 10000000;

void solve(){
	int i,j,k,v;
	int total;
	double max_pb = 0;
	int min;
	bool found;
	for(i = 0; i < sorted_devs.size(); i++){
		total = 0;
		for(j = 0; j < devs.size(); j++){
			min = MIN_PRICE;
			found = false;
			for(k = 0; k < devs[j].size(); k++){
				//find the min price device of all the band santified devices
				if(&devs[j][k] == &sorted_devs[i]){
					min = devs[j][k].p;
					found = true;
					break;
				}
					
				if(devs[j][k].b >= sorted_devs[i].b && devs[j][k].p < min ){
					min = devs[j][k].p;
					found = true;
				}
			}

			if(found){//found, add the min price to the total,and consider the other devices
				total += min;
			}else{//not found the manufacturer in the device 
				break;
			}
		}
		//calculate the min of the min{bi} / sum(pi)
		if(found){
			double pb =  sorted_devs[i].b * 1.0 / total;
			if(max_pb < pb)
				max_pb = pb;
		}else{
			break;//the more band width is not possible
		}
	}
	cout.setf(ios::fixed,ios::floatfield);
	cout.precision(3);
	cout << max_pb << endl;
}

int main(){
	int ncases;
    
	cin >> ncases;
	while(ncases--){
		int i,j,n,m;
		cin >> n;
		devs.clear();
		sorted_devs.clear();
		for(i = 0; i < n; i++){
			vector<Device> v;
			cin >> m;
			for(j = 0; j < m; j++){
				Device d;
				cin >> d.b >> d.p;
				v.push_back(d);
				sorted_devs.push_back(d);
			}
			devs.push_back(v);
		}
		sort(sorted_devs.begin(), sorted_devs.end(),cmp);		
		solve();
	}
	return 0;
}