[PJWSTK] ASD – Projekt 2 – Rozwiązanie

Drugi projekt z ASD:

Rozważmy nieskierowany pełny graf ważony G=(V,E,w), gdzie V={v(0), v(1), …, v(n-1)} jest zbiorem wierzchołków grafu. Waga krawędzi w(i,j) łączącej pewne dwa wierzchołki grafu v(i) oraz v(j) jest równa

w(i,j)=((i+1)*(j+1)) mod p + 1,

gdzie p jest zadaną dodatnią liczbą naturalną. Dalej pajączkiem nazywamy acykliczny podzbiór krawędzi grafu Gpowstały zgodnie z następującym schematem:

• krok 1: wybieramy pewien podzbiór startowy V’ zbioru wierzchołków V i tworzymy początkowo pusty zbiór krawędzi E’,
• krok 2: spośród wszystkich niewykluczonych krawędzi incydentnych z dowolnym wierzchołkiem zbioru V’wybieramy krawędź (v’,w’) o minimalnej wadze, remisy rozstrzygamy zgodnie z porządkiem < na liczbach utworzonych z etykiet wierzchołków krańcowych krawędzi uporządkowanych w kolejności niemalejącej i zapisanych w systemie n-arnym, np. dla krawędzi (34,111) i (122,17) mamy odpowiednio 17 122 < 34 111,
• krok 3: jeżeli zbiór E’ powiększony o wybrana krawędź (v’,w’) tworzy acykliczny podzbiór krawędzi grafu G, to do zbioru E’ dodajemy tą właśnie krawędź, a zbiór V’ powiększamy o wierzchołki krańcowe rozważanej krawędzi, odpowiednio v’ oraz w’ (suma algebraiczna zbiorów V’ i {v’,w’}), następnie krawędź (v’,w’) uznajemy zawykluczoną,
• krok 4: jeżeli istnieje o najmniej jedna niewykluczona krawędź incydentna z dowolnym wierzchołkiem ze zbioruV’, to powracamy do kroku 2, w przeciwnym przypadku pajączka uznajemy za nieaktywnego.

Dalej zbiór S={s(0), s(1), …, s(k-1)} jest zbiorem pajączków. Ustal ostateczną liczbę krawędzi składowych oraz łączną sumę wag krawędzi składowych każdego z k pajączków przyjmując następujący schemat równoczesnej konstrukcji pajączków:

• krok I: dla każdego z pajączków wykonaj krok 1,
• krok II: spośród wszystkich aktywnych pajączków wybieramy pajączka s’, którego aktualna suma wag krawędzi składowych jest minimalna, remisy rozstrzygamy na korzyść pajączka o mniejszym indeksie,
• krok III: dla pajączka s’ wykonujemy jednokrotnie złożenie kroków 2, 3 i 4,
• krok IV: jeżeli istnieje co najmniej jeden aktywny pajączek, to powracamy do kroku II, w przeciwnym przypadku kończymy działanie algorytmu,

zakładając, że krawędź użyta przez dowolnego pajączka (tj. włączona do stosownego zbioru E’) nie może być ponownie użyta przez żadnego innego pajączka.

Wejście

Kolejno:

• liczba naturalna dodatnia definiująca liczbę 1<=n<=10^3 wierzchołków grafu G, znak nowego wiersza/linii (ASCII kod 10),
• liczba naturalna dodatnia definiująca liczbę 1<=p<=10^6, znak nowego wiersza/linii (ASCII kod 10),
• liczba naturalna dodatnia definiująca liczbę 1<=k<=10^3 pajączków, znak nowego wiersza/linii (ASCII kod 10),
• ciąg k wierszy postaci liczba naturalna l znak odstępu/spacji (ASCII kod 32) ciąg l liczb naturalnych v1, v2, …, vl, oddzielonych znakiem odstępu/spacji (ASCII kod 32) i zakończonych znakiem nowego wiersza/linii (ASCII kod 10), gdzie l jest licznością zbioru startowego V’ każdego kolejnego pajączka począwszy od s(0) do s(k-1)włącznie, a v1, v2, …, vl jest postacią tego zbioru (ciąg elementów zbioru).

Wyjście

Ciąg k wierszy postaci liczba naturalna x znak odstępu/spacji (ASCII kod 32) liczba naturalna y znak nowego wiersza/linii (ASCII kod 10), gdzie x jest ostateczną liczbą krawędzi składowych a y jest łączną sumą wag krawędzi składowych każdego kolejnego pajączka począwszy od s(0) do s(k-1) włącznie.

Złożoności i limity

Koszt czasowy i pamięciowy rozwiązania ograniczony przez limity dostępnego czasu i dostępnej pamięci ustalone dla rozważanego zadania na automatycznej platformie sprawdzającej.

Przykład 1

Wejście:
4
5
1
2 0 1

Wyjście:
3 8

Przykład 2

Wejście:
5
7
2
2 0 2
1 4

Wyjście:
4 15
4 18

Rozwiązanie w Javie:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
import java.util.ArrayList;

class Edge
{
    short node_1 = 0;
	short node_2 = 0;
	int points = 0;

	Edge(short node_1, short node_2, int points)
	{
		this.node_1 = node_1;
		this.node_2 = node_2;
		this.points = points;
	}
};

class EdgesSorter implements Comparator<Edge>
{
	@Override
	public int compare(Edge edge_1, Edge edge_2)
	{
		if(edge_1.points != edge_2.points)
		{
			return edge_1.points - edge_2.points;
		}
		else
		{
			return edge_1.node_1 - edge_2.node_1;
		}
	}
}

class Spider
{
	short id = 0;
	int points = 0;
	short edgesCount = 0;
	boolean[] nodes = null;
	short[] parentNode = null;
	Spider(short id)
	{
		this.id = id;
		nodes = new boolean[Main.nodesCount];
		parentNode = new short[Main.nodesCount];
	}
}

public class Main
{
	static int nodesCount = 0;
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		nodesCount = scanner.nextInt();
		int pNumber = scanner.nextInt();
		short spidersCount = scanner.nextShort();
		Spider[] spidersList = new Spider[spidersCount];
		Spider[] sortedSpiders = new Spider[spidersCount];
		short spiderNodesCount = 0;
		Spider spider = null;
		for(short spiderID = 0; spiderID < spidersCount; spiderID++)
		{
			spider = new Spider(spiderID);
			spidersList[spiderID] = spider;
			sortedSpiders[spiderID] = spider;
			spiderNodesCount = scanner.nextShort();
			boolean[] nodes = new boolean[nodesCount];
			while(spiderNodesCount-- > 0)
			{
				nodes[scanner.nextShort()] = true;
			}
			spider.nodes = nodes;
			short[] parentNode = new short[nodesCount];
			for(short node = 0; node < nodesCount; node++)
			{
				parentNode[node] = node;
			}
			spider.parentNode = parentNode;
		}
		List<Edge> edgesList = new ArrayList<Edge>();
		for(short node_1 = 1; node_1 <= nodesCount; node_1++)
		{
			for(short node_2 = (short) (node_1+1); node_2 <= nodesCount; node_2++)
			{
				edgesList.add(new Edge((short) (node_1 - 1), (short) (node_2 - 1), ((node_1 * node_2) % pNumber) + 1));
			}
		}
		Collections.sort(edgesList, new EdgesSorter());
		short topParent_1 = 0;
		short topParent_2 = 0;
		short activeSpidersCount = spidersCount;
		boolean deactiveSpider = true;
		short highestPrioritySpiderID = 0;
		short tmpNode = 0;
		while(activeSpidersCount > 0)
		{
			for(short activeSpiderID = 0; activeSpiderID < activeSpidersCount; activeSpiderID++)
			{
				spider = spidersList[activeSpiderID];
				Spider mSpider = spidersList[highestPrioritySpiderID];
				if(spider.points < mSpider.points || (spider.points == mSpider.points && spider.id < mSpider.id))
				{
					highestPrioritySpiderID = activeSpiderID;
				}
			}
			spider = spidersList[highestPrioritySpiderID];
			deactiveSpider = true;
			for(Edge edge : edgesList)
			{
				if(spider.nodes[edge.node_1] == true || spider.nodes[edge.node_2] == true)
				{
					tmpNode = edge.node_1;
					topParent_1 = spider.parentNode[tmpNode];
					while(tmpNode != topParent_1)
					{
						tmpNode = topParent_1;
						topParent_1 = spider.parentNode[topParent_1];
					}
					tmpNode = edge.node_2;
					topParent_2 = spider.parentNode[tmpNode];
					while(tmpNode != topParent_2)
					{
						tmpNode = topParent_2;
						topParent_2 = spider.parentNode[topParent_2];
					}
					if(topParent_1 != topParent_2)
					{
						spider.nodes[edge.node_1] = true;
						spider.nodes[edge.node_2] = true;
						spider.points += edge.points;
						spider.edgesCount++;
						spider.parentNode[topParent_1] = topParent_2;
						deactiveSpider = false;
						edgesList.remove(edge);
						break;
					}
				}
			}
			if(deactiveSpider)
			{
				spidersList[highestPrioritySpiderID] = spidersList[--activeSpidersCount];
			}
			highestPrioritySpiderID = 0;
		}
		for(Spider sortedSpider : sortedSpiders)
		{
			System.out.println(sortedSpider.edgesCount + " " + sortedSpider.points);
		}
	}
}