Tấn công thành trì

 avatar
user_4303798
c_cpp
a year ago
2.4 kB
11
Indexable
#include<iostream>

const int MAXSIZE = 100;

int graph[MAXSIZE][MAXSIZE];
int visit[MAXSIZE];
int parent[MAXSIZE];
bool hasCycle;


void resetVisit(int numFortress)
{
	for (int i = 0; i < numFortress; i++)
	{
		visit[i] = 0;
	}
}

void resetGraph(int numFortress)
{
	for (int i = 0; i < numFortress; i++)
	{
		for (int j = 0; j < numFortress; j++)
		{
			graph[i][j] = 0;
		}
	}
}

void readInput(int numFortress)
{
	resetGraph(numFortress);

	for (int i = 0; i < numFortress; i++)
	{
		int id, numCannon, connectCount;
		std::cin >> id >> numCannon >> connectCount;

		for (int j = 0; j < connectCount; j++)
		{
			int connectTo;
			std::cin >> connectTo;
			graph[id][connectTo] += numCannon; // weighted graph
			graph[connectTo][id] += numCannon;
		}
	}
}

void resetParent(int numFortress)
{
	for (int i = 0; i < numFortress; i++)
	{
		parent[i] = i;
	}
}

int result = 0;
int findMinEdge(int v, int numFortress)
{
	int min = graph[v][parent[v]];
	int minP = v;

	for (int i = parent[v]; i != v ; i = parent[i])
	{
		if (graph[i][parent[i]] < min)
		{
			min = graph[i][parent[i]];
			minP = i;
		}
	}

	graph[minP][parent[minP]] = graph[parent[minP]][minP] = 0;
	return min;
}

void DFS_help(int v, int numFortress)
{
	if (hasCycle)
	{
		return;
	}
	for (int i = 0; i < numFortress; i++)
	{
		if (graph[v][i] != 0)
		{
			if (visit[i] == 2 && parent[v] != i)
			{
				parent[i] = v;
				result += findMinEdge(i, numFortress);
				hasCycle = true;
				return;
			}
			else if (visit[i] == 0)
			{
				visit[i] = 2;
				parent[i] = v;
				DFS_help(i, numFortress);
				visit[i] = 1;
			}
			
			if (hasCycle)
			{
				break;
			}
		}
	}
	return;
}


void attack_help(int numFortress)
{
	result = 0;
	while (true)
	{
		for (int i = 0; i < numFortress; i++)
		{
			resetVisit(numFortress);
			//resetParent(numFortress);
			hasCycle = false;
			if (visit[i] == 0 )
			{
				parent[i] = -1;
				visit[i] = 2;
				DFS_help(i, numFortress);
			}
		}
		if (!hasCycle)
		{
			break;
		}
	}

	return;
}

int main()
{
	freopen("input.txt", "r", stdin);

	int test;
	std::cin >> test;
	for (int t = 0; t < test; t++)
	{
		int numFortress;
		std::cin >> numFortress;

		readInput(numFortress);
		attack_help(numFortress);
		std::cout << result << "\n";
	}

	return 0;
}
Editor is loading...
Leave a Comment