Brief description :

Cause the favorable concession… the local shop has been booming these days. The reason is customer could buy some item cheaper if she buy some one first, Give you the shopping list and those pair lists, Your task is to determine a order that minimize the total cost.
(You are not be able to buy the item which doesn’t on the shopping list, even if it can help you reduce the total cost… )

Analyse :

This problem statement is similar to the Problem K – Karl’s shopping, which is on the year before last’s IPSC. But this time you no longer use coupons, but the purchase order to get favorable.

Now, Let we talk about the Directed Minimum Spanning Tree directly… In this problem, we first notice our shopping list has many different quantities. We should Delete the 0-quantity item without hesitating, and sum up the Minimum Bargain Price multiply with the Quatity Minus 1 as a boundary, because When we finished the main course, we have already buy each necessary item once, so from now we could buy any item with the lowest price.

We also need to draw a Super Source as a root, and link it to every item with their original price. Don’t forget to add some code to remove those self-circles, this also been required in the beginning.

…
..

.

#include 
#include 
#include 
#include 
using namespace std;

const int INF = 0x7f7f7f7f;
const int N = 51;


struct edge{
	int p, w;
	edge(int a, int b):p(a), w(b){}
};

vector adj[2*N];
int Pred[2*N], Cost[2*N], Label[2*N], Belong[2*N];
// Vertex-List include the Origianl n-Vertex and the Genetate Circle ... (which is at most n/2 + 1)..
// P, C, L, B were used in the Detect course...

int Cur[2*N];
//Current Point Array stands to those vertices is now in the Graph .


int p[N], q[N], b[N];
// the original price, the quantity need to purchase ...
// minimum-price as a bargain ...

int n, m, root, mst;







void addEdge(int x, int y, int w){
	adj[x].push_back(edge(y, w));
}

void Insert(int x){
	Cur[n++] = x;
}

void Delete(int x){
	swap(Cur[x], Cur[--n]);
}


bool Jellyfish(){
	// Generate Predecessor ..
	
	memset(Cost, 0x7f, sizeof(Cost));
	memset(Pred, 0, sizeof(Pred));
	
	for (int i=0;i
External link :


http://mail.bashu.cn:8080/BSoiOnline/showproblem?problem_id=1899
http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html
                                                												

													Posted by 
													xiaodao													
													Category: 													日常