大致題意：
某公司要建立一套通信系統，該通信系統需要n種設備，而每種設備分別可以有m1、m2、m3、...、mn個廠家
提供生產，而每個廠家生產的同種設備都會存在兩個方面的差別：帶寬bandwidths 和 價格prices。
現在每種設備都各需要1個，考慮到性價比問題，要求所挑選出來的n件設備，要使得B/P最大。
其中B為這n件設備的帶寬的最小值，P為這n件設備的總價。
解題思路：
首先需要明確，要使得B/P最大，自然是要令B盡可能大，P盡可能小。
由於B和P是兩個相互制約的變量，而他們又要同時取得盡可能地取極值，那麼可以先令其中一個值“暫時固定”下來。
令輸入的行數就是設備的種類數，即第i行描述的是第i種設備，及提供第i種設備的廠家的產品信息。
使用枚舉+剪枝的做法：
首先B的值肯定是廠家生產的所有設備中的某個帶寬值,所以可以枚舉所有的帶寬，每次枚舉B值時，B值就被“暫時固定”了。
其次，記錄所選取的B是屬於第k種設備的，再從余下的設備中，選取其余n-1種設備各一個，要求所選取的設備的帶寬>=B（這是由題意確定的），而價格是要滿足帶寬的要求下的最小值。
當n種設備都選取後，計算B/P，然後再枚舉下一個B，重復上述操作。比較不同的B值所得到的B/P值，選取最大的一個就是答案。
剪枝法：
准備工作：
1、輸入時先記錄：對於每種設備，廠家所提供的最大帶寬MaxB[]
2、對所有設備（無論是否同種類）進行升序快排，以帶寬為第一關鍵字，價格為第二關鍵字，設備所屬的種類編號(1~n)為第三關鍵字。排序後存放在一維數組dev[]
剪枝：
1、 從小到大枚舉dev[]中各個設備的帶寬作為B值，設總設備數位m，則從1枚舉到m-(n-1)。這是因為至少需要選擇從枚舉位置開始後面的n種設備，m-(n-1)是上限值，即恰好最後n件設備分別為n種設備。
2、 枚舉B值的過程中，若發現B值比某種設備的最大帶寬更大，則無需繼續枚舉，輸出前面得到的B/P值。這是因為B是所有設備的最小帶寬，若出現某個設備的最大帶寬比B小，則說明B的選擇是不合法的，又dev[]已按B升序排序，後面的B值更大，也不可能成立，因此無需繼續枚舉。
3、 枚舉B值過程中，對於每個B值，在選擇其他設備時要記錄選取不同種類的設備個數count。最後當count<n時，說明B值位置往後剩余的設備中已無法提供n-1種不同設備，可直接跳出枚舉。
-----------------------------//上面分析轉自：優YoU http://blog.csdn.net/lyy289065406/article/details/6676781
我的代碼：
P.S. 在HDU上用GNU C++ 一直是 WA ，但是在POJ上用 C++ 交就能過（
Accepted 312K 110MS C++
），真心搞不懂。。
[cpp]
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101
struct NODE
{
int b;//寬帶
int p;//價格
int id;//設備編號
};
//按帶寬、價格、編號依次比較排序
int cmp(const void* a, const void* b)
{
NODE* x =(NODE*)a;
NODE* y =(NODE*)b;
if((x->b)==(y->b))
{
if((x->p)==(y->p))
return (x->id) -(y->id);
else
return (x->p) - (y->p);
}
return (x->b) -(y->b);
}
double max(double a, double b)
{
return a > b? a:b;
}
int MaxB[N]; //各種設備對應的帶寬最大值
NODE dev[N*N]; //記錄所有廠家生產的產品信息
bool vist[N];
int pd; //dev[]指針
int main()
{
int test, i, j;
//freopen("in.txt","r",stdin);
scanf("%d",&test);
while(test--)
{
int n;//設備數
int m = 0; //生產商總數
pd = 0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
int mi;
scanf("%d",&mi);
m +=mi;
MaxB[i] =-1;
for(j=1;j<=mi;j++)
{
pd++;
scanf("%d%d",&dev[pd].b,&dev[pd].p);
dev[pd].id=i;
MaxB[i] = max(MaxB[i], dev[pd].b);
}
}
qsort(dev,m+1,sizeof(NODE),cmp);
bool flag = false;
double ans = 0; // B/P的最大值
for(i=1;i<=m-(n-1);i++) //枚舉所有設備帶寬的最小帶寬B
{ //m-(n-1)是剪枝，因為當設備數>生產商時就不必枚舉了
memset(vist,false,sizeof(bool)*(n+1));
vist[dev[i].id] = true;
double price = dev[i].p; //設備總價
int count = 1; //計數器，記錄已經選取的設備個數
for(j=i+1;j<=m;j++)
{
if(vist[ dev[j].id])
continue;
if(dev[i].b > MaxB[dev[j].id]) //剪枝
{
flag= true; //當前枚舉的“所有設備帶寬的最小帶寬Bi”比“設備j的最大帶寬MaxBj”要大
//說明當前Bi已經越界，無需繼續往後枚舉
break;
}
vist[dev[j].id] =true;
price +=dev[j].p;
count++;
}
if(flag || count<n)
break;
ans = max(ans, (dev[i].b/price));
}
printf("%.3lf\n",ans);
}
return 0;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101
struct NODE
{
int b;//寬帶
int p;//價格
int id;//設備編號
};
//按帶寬、價格、編號依次比較排序
int cmp(const void* a, const void* b)
{
NODE* x =(NODE*)a;
NODE* y =(NODE*)b;
if((x->b)==(y->b))
{
if((x->p)==(y->p))
return (x->id) -(y->id);
else
return (x->p) - (y->p);
}
return (x->b) -(y->b);
}
double max(double a, double b)
{
return a > b? a:b;
}
int MaxB[N]; //各種設備對應的帶寬最大值
NODE dev[N*N]; //記錄所有廠家生產的產品信息
bool vist[N];
int pd; //dev[]指針
int main()
{
int test, i, j;
//freopen("in.txt","r",stdin);
scanf("%d",&test);
while(test--)
{
int n;//設備數
int m = 0; //生產商總數
pd = 0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
int mi;
scanf("%d",&mi);
m +=mi;
MaxB[i] =-1;
for(j=1;j<=mi;j++)
{
pd++;
scanf("%d%d",&dev[pd].b,&dev[pd].p);
dev[pd].id=i;
MaxB[i] = max(MaxB[i], dev[pd].b);
}
}
qsort(dev,m+1,sizeof(NODE),cmp);
bool flag = false;
double ans = 0; // B/P的最大值
for(i=1;i<=m-(n-1);i++) //枚舉所有設備帶寬的最小帶寬B
{ //m-(n-1)是剪枝，因為當設備數>生產商時就不必枚舉了
memset(vist,false,sizeof(bool)*(n+1));
vist[dev[i].id] = true;
double price = dev[i].p; //設備總價
int count = 1; //計數器，記錄已經選取的設備個數
for(j=i+1;j<=m;j++)
{
if(vist[ dev[j].id])
continue;
if(dev[i].b > MaxB[dev[j].id]) //剪枝
{
flag= true; //當前枚舉的“所有設備帶寬的最小帶寬Bi”比“設備j的最大帶寬MaxBj”要大
//說明當前Bi已經越界，無需繼續往後枚舉
break;
}
vist[dev[j].id] =true;
price +=dev[j].p;
count++;
}
if(flag || count<n)
break;
ans = max(ans, (dev[i].b/price));
}
printf("%.3lf\n",ans);
}
return 0;
}
