問題背景
面對艱巨復(fù)雜的技術(shù)挑戰(zhàn)，百度所崇尚的系統(tǒng)設(shè)計哲學(xué)是“簡單可依賴”，而百度的工程師們正在互聯(lián)網(wǎng)世界中實踐著這種理念。這里正好有一個挑戰(zhàn)，讓作為百度之星的你小試牛刀：
在處理數(shù)以百億計的網(wǎng)絡(luò)信息的過程中，有一個很常見的問題：
怎么樣將一個集群上的信息以最低的成本傳輸?shù)搅硗庖粋€集群上？
數(shù)據(jù)源集群A有n臺服務(wù)器，編號為 1, 2, ..., n，i號服務(wù)器上待傳輸?shù)臄?shù)據(jù)量為Ai ，單位是GB。
目的地集群B有m臺服務(wù)器，編號為 1, 2, ..., m，j號服務(wù)器上的空閑容量為 Bj，單位為 GB。
A集群的i號服務(wù)器上的每GB數(shù)據(jù)對于B的集群的j號服務(wù)器收益為Vi,j，從 A 集群的 i 號服務(wù)器向 B 集群的 j 號服務(wù)器傳輸 1GB數(shù)據(jù)的開銷為Ci,j。
你的任務(wù)是在保證A中的所有數(shù)據(jù)傳輸完畢的前提下，性價比V/C盡量高。其中V為所有數(shù)據(jù)在B集群上的價值之和，C為總開銷。換句話說，若A集群的i號服務(wù)器向B集群的j號服務(wù)器發(fā)送了Ti,j個GB的數(shù)據(jù)（Ti,j不一定是整數(shù)），則性價比定義為：
輸入格式
第1行兩個整數(shù)n, m(1<=n,m<=50)，即集群A和B各自的服務(wù)器臺數(shù)。
第2行包含n個不超過100的正整數(shù)A1,A2,…,An，即集群A中每臺服務(wù)器的待傳輸數(shù)據(jù)量（單位：GB）。
第3行包含m個不超過100的正整數(shù)B1,B2,…,Bm，即集群B中每臺服務(wù)器所能接受的最大數(shù)據(jù)量（單位：GB）。
第 4 ~ n+3 行每行包含m個不超過100的非負(fù)整數(shù)Vi,j，表示集群A的i號服務(wù)器中每GB數(shù)據(jù)對于集群B中的j號服務(wù)器的價值。
第 n+4 ~ 2n+3 行每行包含m個不超過100的正整數(shù)Ci,j，表示集群A的i號服務(wù)器中每GB數(shù)據(jù)傳輸?shù)郊築中的j號服務(wù)器所需要的開銷。
輸出格式
僅一行，為最大性價比。輸出保留三位小數(shù)（四舍五入）。如果A的數(shù)據(jù)無法傳輸完畢，輸出字符串 “-1”（無引號）。
樣例輸入
2 2
1 2
2 1
11 0
7 5
6 1
3 2
樣例輸出
2.091
樣例解釋
一個方案是：
集群A的1號服務(wù)器把所有數(shù)據(jù)傳輸?shù)郊築的1號服務(wù)器，價值11，開銷6。
集群A的2號服務(wù)器把1GB數(shù)據(jù)傳輸?shù)郊築的1號服務(wù)器，價值7，開銷3，然后把剩下的1GB數(shù)據(jù)傳輸?shù)郊築的2號服務(wù)器，價值5，開銷2。
性價比：(11+7+5)/(6+3+2)=2.091
另一個方案是：
集群A的1號服務(wù)器把所有數(shù)據(jù)傳輸?shù)郊築的2號服務(wù)器，價值0，開銷1。
集群A的2號服務(wù)器把所有數(shù)據(jù)傳輸?shù)郊築的1號服務(wù)器，價值14，開銷6。
性價比：(0+14)/(1+6)=2。
第一種方案更優(yōu)
我的解答：
該題應(yīng)該是貪心法可解，每次求性價比最高的，跟部分背包問題很像。
可惜不是，子問題不是獨立的，我的解法肯定不是最優(yōu)解。sign~~~，據(jù)說是最大流的問題，改天研究研究。
我的解法用了N+1個最大值堆，一個是全局所有為傳輸完的源站點的最高性價比方案，
其余每個源站點一個最大值堆含該站點所有傳輸方案。
//============================================================================
// Name : TransportOpt.cpp
// Author : Yovn
// Version :
// Copyright : yovnchine@gmail.com
//============================================================================
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;
int numA;
int numB;
int* valuesA;
int* valuesB;
int** values=NULL;
int** costs=NULL;
typedef struct _HeapNode
{
int a;
int b;
float vPerC;
}HeapNode;
class MaxHeap
{
public:
MaxHeap(int n):nodes(new HeapNode[n]),total(n),len(0){
}
MaxHeap():nodes(NULL),total(0),len(0){
}
~MaxHeap()
{
delete[] nodes;
}
bool isEmpty()
{
return len<=0;
}
void setSize(int n)
{
nodes=new HeapNode[n];
total=n;
len=0;
}
HeapNode removeMax()
{
HeapNode ret=nodes[0];
nodes[0]=nodes[--len];
shift_down(0);
return ret;
}
void insert(HeapNode val)
{
nodes[len++]=val;
shift_up(len-1);
}
private :
void shift_up(int pos) {
HeapNode tmp=nodes[pos];
int index=(pos-1)/2;
while (index>=0) {
if (tmp.vPerC>nodes[index].vPerC) {
nodes[pos]=nodes[index];
pos=index;
if (pos==0)
break;
index=(pos-1)/2;
} else
break;
}
nodes[pos]=tmp;
}
void shift_down(int pos) {
HeapNode tmp=nodes[pos];
int index=pos*2+1;//use left child
while (index<len)//until no child
{
if (index+1<len&&nodes[index+1].vPerC>nodes[index].vPerC)//right child is smaller
{
index+=1;//switch to right child
}
if (tmp.vPerC<nodes[index].vPerC) {
nodes[pos]=nodes[index];
pos=index;
index=pos*2+1;
} else {
break;
}
}
nodes[pos]=tmp;
}
HeapNode* nodes;
int total;
int len;
};
void parseToInts(string& line, int* arr, int num) {
int pos=0;
for (int i=0; i<line.length(); i++) {
if (line[i]>='0'&&line[i]<='9') {
if (line[i+1]>='0'&&line[i+1]<='9') {
int a=(line[i]-'0')*10+(line[i+1]-'0');
arr[pos++]=a;
i++;
} else {
int a=(line[i]-'0');
arr[pos++]=a;
}
}
}
}
void input()
{
string line;
getline(cin,line);
sscanf(line.c_str(),"%d %d",&numA,&numB);
valuesA=new int[numA];
valuesB=new int[numB];
line.clear();
getline(cin,line);
parseToInts(line,valuesA,numA);
line.clear();
getline(cin,line);
parseToInts(line,valuesB,numB);
values=new int*[numA];
costs=new int*[numA];
for (int i=0; i<numA; i++) {
values[i]=new int[numB];
line.clear();
getline(cin, line);
parseToInts(line, values[i], numB);
}
for (int i=0; i<numA; i++) {
costs[i]=new int[numB];
line.clear();
getline(cin, line);
parseToInts(line, costs[i], numB);
}
}
bool validate() {
int sumA=0, sumB=0;
for (int i=0; i<numA; i++) {
sumA+=valuesA[i];
}
for (int i=0; i<numB; i++) {
sumB+=valuesB[i];
}
return sumA<=sumB;
}
void calc() {
MaxHeap totalHeap(numA);
MaxHeap* aHeaps=new MaxHeap[numA];
int totalC=0;
int totalV=0;
if(!validate())
{
printf("-1\n");
return;
}
for (int i=0; i<numA; i++) {
aHeaps[i].setSize(numB);
for(int j=0;j<numB;j++)
{
HeapNode node;
node.a=i;
node.b=j;
node.vPerC=(float)values[i][j]/(float)costs[i][j];
aHeaps[i].insert(node);
}
totalHeap.insert(aHeaps[i].removeMax());
}
while(!totalHeap.isEmpty())
{
HeapNode node=totalHeap.removeMax();
if(valuesA[node.a]==valuesB[node.b])
{
totalV+=values[node.a][node.b]*valuesA[node.a];
totalC+=costs[node.a][node.b]*valuesA[node.a];
valuesB[node.b]=0;
valuesA[node.a]=0;
}
else if(valuesA[node.a]>valuesB[node.b])
{
totalV+=values[node.a][node.b]*valuesB[node.b];
totalC+=costs[node.a][node.b]*valuesB[node.b];
valuesA[node.a]-=valuesB[node.b];
valuesB[node.b]=0;
}
else
{
totalV+=values[node.a][node.b]*valuesA[node.a];
totalC+=costs[node.a][node.b]*valuesA[node.a];
valuesB[node.b]-=valuesA[node.a];
valuesA[node.a]=0;
}
while(!aHeaps[node.a].isEmpty())
{
HeapNode todo=aHeaps[node.a].removeMax();
if(valuesA[todo.a]>0&&valuesB[todo.b]>0)
{
totalHeap.insert(todo);
break;
}
}
}
printf("%lf\n",(float)totalV/totalC);
}
int main() {
input();
calc();
return 0;
}