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);
}
}
}