Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
1
Indexable
Never
#include <iostream>
using namespace std;

#define MAX 100000
class Queue
{
	int front;
	int near;
	int a[MAX];
public:	
	Queue();
	bool EnQueue(int x);
	bool isEmpty();
	bool fullQueue();
	int DeQueue();
	int peek();
	void reset();
};
Queue::Queue()
{
	front = -1;
	near = -1;
}
bool Queue::fullQueue()
{
	return (MAX-1 == this->near);
}
bool Queue::isEmpty()
{
	return (this->near == this->front);
}
bool Queue::EnQueue(int x)
{
	if(this->fullQueue())
		return false;
	this->a[++this->near] = x;
	return true;
}
int Queue::DeQueue()
{
	if(this->isEmpty())
		return -1;
	return this->a[++this->front];
}
int Queue::peek()
{
	if(this->isEmpty())
		return -1;
	return this->a[this->front+1];
}
void Queue::reset()
{
	front = -1;
	near = -1;
}
struct Node
{
	int x,y,diem;
};

Node nodeDC[100];
Node nodeNH[20];
Queue queueX;
Queue queueY;
int K,R,M,N;
int arr[1000][1000];
int arrKhoangCach[100][100];
int visitNH[20];
int visitDC[100];
int Max;
int Sum;

bool kc(int i, int j)
{
	int k = (nodeNH[i].x - nodeDC[j].x)*(nodeNH[i].x - nodeDC[j].x) + (nodeNH[i].y - nodeDC[j].y)*(nodeNH[i].y - nodeDC[j].y);
	return (k <= R*R);
}

void removeCus(int i)
{
	for(int j = 0 ; j < N ; j++)
	{
		if(visitDC[j] == i+1)
		{
			Sum -= nodeDC[j].diem;
			visitDC[j] = 0;
		}
	}
}

bool addCus(int i)
{
	bool change = false;
	for(int j = 0 ; j < N ; j++)
	{
		if(visitDC[j] == 0)
		{
			if(kc(i,j))
			{
				change = true;
				Sum += nodeDC[j].diem;
				visitDC[j] = i+1;
			}
		}
	}
	return change;
}
bool haveCus()
{
	bool check = false;
	for(int i = 0 ; i < N ; i++)
		if(visitDC[i]==0)
		{
			check = true;
			break;
		}
	return check;
}
void solve(int index)
{
	if(index == K || !haveCus())
	{
		if(Sum > Max) Max = Sum;
		return;
	}
	for(int i = 0 ; i < M ; i++)
	{
		if(visitNH[i] == 0)
		{
			visitNH[i] = 1;
			if(addCus(i)){
			solve(index+1);
			removeCus(i);
			}
			visitNH[i] = 0;
		}		
	}
}
void resetvisit()
{
	for(int i = 0 ; i < 100 ; i++)
	{
		visitDC[i] = 0;
	}
	for(int i = 0 ; i < 20 ; i++)
	{
		visitNH[i] = 0;
	}
}
int main()
{
//	freopen("input.txt" , "r" , stdin);
	int T;
	cin >> T;
	for(int testCase = 1; testCase <= T ; testCase++)
	{
		//reset visit
		resetvisit();
		cin >> K >> R;
		cin >> M;
		for(int i = 0 ; i < M ; i++)
		{
			cin >> nodeNH[i].x >> nodeNH[i].y;	
		}
		cin >> N;
		for(int i = 0 ; i < N ; i++)
		{
			cin >> nodeDC[i].x >> nodeDC[i].y >> nodeDC[i].diem;
		}
		Sum = 0;
		Max = -1;
		solve(0);
		cout << "#" << testCase << " "<< Max << endl;
	}
	return 0;
}