Algorithms on graphs

Plus

Problem description Progress

ID 33226. Количество дорог

Напишите программу, которая считает количество дорог в городе Новые Васюки. Схема дорог задана как матрица смежности графа. На некоторых дорогах введено одностороннее движение.

Входные данные

В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы матрицы смежности графа, который описывает схему дорог.

Выходные данные

Программа должна вывести одно число – количество дорог в Новых Васюках. Дороги с двусторонним движением нужно считать только один раз.

Ввод	Вывод
5 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0	7

ID 33227. Суммарная длина дорог

Темы: Algorithms on graphs

Найдите суммарную длину всех дорог в городе Новые Васюки. Схема дорог задана в виде весовой матрицы графа. На некоторых дорогах введено одностороннее движение. Если длины дорог из пункта А в пункт Б разные, это означает, что есть две разные дороги.

Входные данные

В первой строке вводится количество перекрёстков в Новых Васюках N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – длины дорог между каждой парой перекрёстков. Ноль означает, что дороги между этими перекрёстками нет.

Выходные данные

Программа должна вывести одно число – суммарную длину дорог. Дороги с двусторонним движением нужно считать только один раз.

Ввод	Вывод
5 0 2 3 4 0 2 0 5 0 7 3 6 0 8 0 0 0 0 0 0 0 7 0 9 0	44

ID 22017. Cities and roads

Темы: Algorithms on graphs

In the "Milky Way" galaxy on the planet "Neptune" there are N cities, some of which are connected by roads. Emperor "Maximus" "Milky Way" galaxy decided to make an inventory of the roads on the planet "Neptune". But as it turns out, he's not good at math, so he asks you to count the number of roads.

Input
The first line specifies the number N (\(0<=N<=100\)). In the following

N< /code> lines contain N numbers, each of which is a one or a zero. Moreover, if the position of the (i,j) square matrix is one, then the i-th and j-th cities are connected by roads,  and if zero, then they are not connected.



 

Output 

Output one number - the number of roads on the planet "Neptune".

 

Note

All roads are two-way, that is, if there is a road from the city i to the city j, then there is a road from the city j to the city i, and it's the same road.
 

Examples




#
Input
Output




1

5

0 1 0 0 0 

1 0 1 1 0 

0 1 0 0 0 

0 1 0 0 0 

0 0 0 0 0

3

ID 22018. Traffic lights-1

Темы: Algorithms on graphs

In the dungeon of M tunnels and N junctions, each tunnel connects some two junctions. The mouse king decided to put a traffic light in each tunnel in front of each intersection. Write a program that will calculate how many traffic lights should be installed at each of the intersections. Crossroads are numbered from 1 to N.

Input
The first line contains two numbers N and M (\(0<N<=100\), \(0<=M<=N*(N-1)/2\) ). The following M lines contain two numbers i and j (\(1<=i,j<=N\)) , which means that the intersections i and j are connected by a tunnel.

Imprint
Print N numbers: kth number means the number of traffic lights at the kth intersection.

Note
We can assume that any two intersections are connected by no more than one tunnel. There are no tunnels from the i intersection to itself.

Examples

#	Input	Output
1	7 10 5 1 3 2 7 1 5 2 7 4 6 5 6 4 7 5 2 1 5 3	3 3 2 2 5 2 3

ID 22019. colored rain

Темы: Algorithms on graphs

There are a lot of hills connected by bridges in the Banana Republic. There was an accident at a chemical plant, as a result of which the experimental fertilizer "zovan" evaporated. The next day, colored rain fell, and it only passed over the hills, in some places red drops fell, in some - blue, and in the rest - green, as a result of which the hills became the corresponding color. The President of the Banana Republic liked this, but he wanted to paint the bridges between the hilltops so that the bridges were painted in the color of the hills they connect. Unfortunately, if the hills are of different colors, then it will not be possible to paint the bridge in this way.
Count the number of such "bad" bridges.

Input:
- the first line contains N (\(0<N<=100\)) - the number of hills;
- then comes the adjacency matrix, which describes the presence of bridges between hills (1-bridge exists, 0-no);

- the last line contains N numbers indicating the color of the hills: 1 - red; 2 - blue; 3 - green.

Output: output the number of "bad" bridges.

Examples

#	Input	Output
1	7 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 3 3	4

ID 33130. Check for disorientation

Темы: Algorithms on graphs

Given a square n×n matrix of zeros and ones, determine whether the given matrix can be an adjacency matrix of a simple undirected graph.

Input:
- the first line contains the number n (\(1<=n<=100\)) – matrix size;
- then the matrix itself is set - n rows of n numbers, each of which is equal to 0 or 1.

Output: print «YES» if the matrix given can be the adjacency matrix of a simple undirected graph, and « ;NO» otherwise.

Examples

#	Input	Output
1	5 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0	YES

ID 33129. loops

Темы: Algorithms on graphs

Given the adjacency matrix of an undirected graph, determine if it contains loops.

Input:
- the first line contains the number n (\(1<=n<=100\)) – number of graph vertices;
- then the adjacency matrix is set - n rows of n numbers, each of which is equal to 0 or 1 .

Output: output "YES" if the graph contains loops, and "NO" otherwise.

Examples

#	Input	Output
1	5 1 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0	YES

ID 33131. Adjacency matrix to edge list, undirected variant

Темы: Algorithms on graphs

A simple undirected graph is defined by an adjacency matrix, print its representation as a list of edges.

Input: Input includes number n (\( 1<= n<=100\)) – the number of vertices in the graph, followed by n rows of n numbers each equal to 0 or 1, &ndash ; its adjacency matrix.

Output: output list of edges of the given graph (in any order).

Examples

#	Input	Output
1	5 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0	1 3 23 25

ID 33132. Edge list to adjacency matrix, undirected variant

Темы: Algorithms on graphs

A simple undirected graph is given a list of edges, output its representation as an adjacency matrix.

Input:
- the first line sets numbers n (\(1<=n<=100\)) – the number of vertices in the graph and m (\(1<=m<=n(n - 1)/2\)) – number of ribs;
- followed by m pairs of numbers – graph edges (each pair of numbers on a separate line).

Output: print the adjacency matrix of the given graph.

Examples

#	Input	Output
1	5 3 1 3 2 3 2 5	0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0

ID 38444. villages

Темы: Dynamic programming Algorithms on graphs Depth walk Dynamic Graph Programming

There are N villages in the thirtieth state. Some pairs of villages are connected by roads. In order to save money, “superfluous” there are no roads, i.e. There is only one way to get from any village to any village by road.
The latest research has shown that the thirtieth state is located in a seismically dangerous zone. Therefore, the head of state wanted to know what kind of damage an earthquake could bring to his country. Namely, he wants to know what is the minimum number of roads that must be destroyed in order to form a group of exactly P villages, isolated from the rest, such that from any village from this group to any other village from this group it will still be possible to get by undestroyed roads (a group is isolated from the rest if no undamaged road connects a village in this group with a village not in this group).
You should write a program to help him with this.

Input data format
The first line of the input file contains two numbers: N and P (1 ≤ P ≤ N ≤ 150). All other lines contain road descriptions, one per line: the road description consists of two village numbers (from 1 to N) that this road connects. All numbers in the input file are separated by spaces and/or newlines.

Output data format
In the output file print a single number — desired number of roads.

Examples

#	Input	Output	Explanation
1	3 2 1 2 3 2	1
2	11 6 1 2 1 3 14 15 26 27 28 49 4 10 4 11	2	A group of villages (1, 2, 3, 6, 7, 8) will be isolated from the rest if roads 1–4 and 1–5 are destroyed.

ID 38512. Highways and roads

Темы: Algorithms on graphs

There are N cities. There are also K highways and L railways running between the cities. Each i-th highway bidirectionally connects p_i and q_i cities, and each i-th railway bidirectionally connects r_i and s_i cities. No two highways connect the same pair of cities. Similarly, no two railroads connect the same pair of cities. We will assume that cities A and B are connected by a highway if city B can be reached from city A on some highway. Here, any city is considered to be connected to a highway. Similarly, we will also define the possibility of communication by railroads. For each city, find the number of cities connected to that city by both highways and railroads.

Input
The input data comes in the following format:

N K L
p₁q₁
...
p_Kq_K
r₁s₁
...
r_ls_L

Restrictions:
\(2<=N<=2\cdot10^5 \\ 1<=K,L<=10^5 \\ 1<=p_i,q_i,r_i,s_i<= N\\ p_i <q_i \\ r_i<s_i \\ When\ i \neq j, (p_i,q_i)\neq(p_j,q_j) \\ ?When\ i \neq j, (r_i,s_i)\neq (r_j,s_j)\)

Imprint
Print N integers on one line, separating each number with one space. Each i number must represent the number of cities connected to the ith city by both highways and railroads.

Examples

#	Input	Output	Explanations
1	4 3 1 1 2 23 34 2 3	1 2 2 1	All four cities are connected by roads. Only the second and third cities are connected by rail. Thus, the answers for cities are 1,2,2 and 1 respectively.
2	4 2 2 1 2 23 14 2 3	1 2 2 1
3	7 4 4 1 2 23 25 67 3 5 4 5 34 6 7	1 1 2 1 2 2 2

ID 38516. Petersburg?

Темы: Interactive tasks Bridges Algorithms on graphs

Error

ID 38521. Candidates for no shortcut

Темы: Algorithms on graphs Shortest paths in a graph

Given an undirected connected weighted graph with N vertices and M edges that contains neither loops nor double edges. I-e (\(1<=i<=M\)) edge connects vertex a_i and the vertex b_i at distance c_i. We will assume that the loop is an edge, where \(a_i=b_i\) (\(1<=i<= M\)), and double edges are two edges where \((a_i,b_i)=(a_j,b_j) \) or \((a_i,b_i)=(b_j,a_j)\) (\(1<=i<j< ;=M\)). A connected graph is a graph in which there is a path between every pair of distinct vertices. Find the number of edges that do not belong to any shortest path between any pair of distinct vertices.< br />
Input
The first line specifies two integers N and M (\(2<=N<=100\) , \(N-1<=M<=min(N \cdot (N-1)/2,1000)\)). This is followed by M lines of three integers per line: a_i, b_i , c_i (\(1<=a_i, b_i<=N\)< /span>, \(1<=c_i<=1000\)). This graph does not contain loops or double edges. This graph is connected .

Imprint
Print the number of edges in the graph that do not belong to any shortest path between any pair of distinct vertices.

Examples

#	Input	Output	Explanations
1	3 3 1 2 1 1 3 1 2 3 3	1	In this graph, the shortest paths between all pairs of distinct vertices are: Shortest path from node 1 to node 2: node 1 → vertex 2, path length is 1. Shortest path from node 1 to node 3: node 1 → vertex 3, path length is 1. Shortest path from node 2 to node 1: node 2 → vertex 1, path length is 1. Shortest path from node 2 to node 3: node 2 → peak 1 → vertex 3, path length is 2. Shortest path from node 3 to node 1: node 3 → vertex 1, path length is 1. Shortest path from node 3 to node 2: node 3 → peak 1 → vertex 2, path length is 2. So the only edge that is not contained in any shortest path is the edge of length 3 connecting vertex 2 and vertex 3, so the output should be 1.
2	3 2 1 2 1 2 3 1	0	Each edge is contained in some shortest path between a pair of distinct vertices.

ID 38585. transit route

Темы: Algorithms on graphs Shortest paths in a graph Bypass in width

You are given a tree with N vertices. Here a tree is a kind of graph, more precisely, a connected undirected graph with N−1 edges, where N is the number of its vertices. Ith edge (\(1<=i<=N-1\)) connects a_{i vertices} and b_i and is c_i.
You are also given Q queries and an integer K. For each jth query (\(1<=j<=Q\)) find the length of the shortest path from the top x_j to vertex y_j via vertex K.

Input
The first line contains an integer N (\(3<=N<=10^5\)). The following N lines contain the vertices a_i and b_i (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\) ) and the length between them c_i(\(1<=c_i<=10^9\ ), \(1<=i<=N-1\))
Next come two numbers Q and K (\(1<=Q<=10^5\), \(1<=K<=N\)). The last Q lines contain integers x_j, y_j (\(x_j \neq y_j\),\(x_j \neq K\), < span class="math-tex">\(y_j \neq K\) \(1<=j<=Q\), ) .
The given graph is a tree.

Imprint
Print responses to queries in Q lines. On the j-th line print the answer to the j-th query.

Examples

#	Input	Output	Explanation
1	5 1 2 1 1 3 1 2 4 1 3 5 1 3 1 24 23 4 5	3 2 4	The shortest paths for the three queries are as follows: Query 1: Vertex 2 → Vertex 1 → Vertex 2 → Vertex 4: Length 1 + 1 + 1 = 3 Query 2: Vertex 2 → Vertex 1 → Vertex 3: Length 1 + 1 = 2 Query 3: Vertex 4 → Vertex 2 → Vertex 1 → Pinnacle 3 → Vertex 5: Length 1 + 1 + 1 + 1 = 4
2	7 1 2 1 1 3 3 1 4 5 1 5 7 1 6 9 1 7 11 3 2 1 3 4 5 6 7	5 14 22	The path for each request must pass through node K = 2.
3	10 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000 1 1 9 10	17000000000

ID 38655. Metro Davilon

Темы: Algorithms on graphs Shortest paths in a graph

Davilon is the largest city on the moon. Davilon has its own metro system, consisting of N stations and M railway lines. The stations are numbered from 1 to N. Each line is operated by a company. Each company has an identification number. The ith (1<=i<=M) line connects station pi and qi bidirectionally. There is no intermediate station. This line is run by ci. You can transfer at stations where there are several lines available. The fare system used in this subway system is a bit odd. When a passenger uses only those lines operated by the same company, the fare is 1 santik (the currency of Davilon). Each time a passenger transfers to a line operated by a company other than the current line, the passenger will be charged an additional fare of 1 centik. In the event that a passenger who switched from the line of company A to the line of another company switches again to the line of company A, the additional fare is charged again. Dunno is now at station 1 and wants to get to station N by metro. Find the minimum required rate.

Input
The first line contains two integers N (2<=N<=10⁵) and M (0<=M<=2*10⁵). Each of the next M lines contains 3 numbers: pi, qi and ci; 1<=pi<=N (1<=i<=M), 1<=qi<=N, 1<=ci<=10⁶, pi ≠ qi.

Imprint
Output the minimum required rate. If it is impossible to get to station N by metro, print -1.

Examples

#	Input	Output	Explanation
1	3 3 1 2 1 2 3 1 3 1 2	1	Use company lines 1: 1 &rr; 2 &rr; 3. The fare is 1 cent.
2	8 11 1 3 1 1 4 2 2 3 1 2 5 1 3 4 3 3 6 3 3 7 3 4 8 4 5 6 1 6 7 5 7 8 5	2	Use company lines first: 1 &rr; 3 &rr; 2 &rr; 5 &rr; 6. Then use company lines 5: 6 &rr; 7 &rr; 8. The fare is 2 cents.
3	2 0	-1

ID 33230. School

Темы: Minimum frame Algorithms on graphs

In order to prepare for the Olympiad in Informatics, the mayor decided to provide all schools in the city with reliable power supply. To do this, it is necessary to conduct a power line from an alternative source of electricity “Maibuttya” to one of the schools in the city (it doesn’t matter which one), as well as to connect some schools with each other by power lines.

A school is considered to have a reliable power supply if it is directly connected to the Maibutcha source, or to one of those schools that has a reliable power supply.

The connection cost between some pairs of schools is known. The mayor of the city decided to choose one of the two most economical power supply schemes (the cost of the scheme is equal to the sum of the costs of connecting pairs of schools).

Write a program that calculates the cost of the two most cost-effective alternative power supply schemes for schools.

Input

The first line of the input file contains two natural numbers separated by a space: N (3 <= N <= 100), the number of schools in the city, and

M – the number of possible connections between them. Each of the following M lines contains three numbers: A_i, B_i, C_i, separated by spaces, where C_i - cost of laying a power line (1 <= C_i <= 300) from school A_i to school B_i (i=1,2,…,N).



 

Output

The single line of the output file must contain two natural numbers S₁ and S₂ separated by a space &ndash ; the two lowest circuit costs (S₁ <= S₂). S₁=S₂ if and only if there are several least cost reliable power supply schemes.

 

It is guaranteed that there are two different reliable power supply schemes for the input data.

 
Examples




#
Input
Output




1

5 8

1 3 75

3 4 51

2 4 19

3 2 95

2 5 42

5 4 31

1 2 9

3 5 66

110 121

ID 44037. Accelerators for Santa Claus

Темы: Dynamic Table Programming Elementary geometry Algorithms on graphs

Santa Claus must visit N cities overnight. He has a two-dimensional plan for the location of all cities. The plan is drawn in Cartesian system of coordinates, in which point (0, 0) indicates the place where Father Frost starts. Each city on the plan is marked with a point with the coordinate ;(X_i, Y_i). Also on the map are marked M points with coordinates (P_i, Q_i) , in which accelerators are located. In order to have time to deliver all the gifts, Santa Claus can use an accelerator that doubles his speed (or maybe not use it).

On New Year's Eve Santa Claus starts from the starting point, visits all N cities and returns.

Father Frost's initial speed is 1. Find the shortest time it takes for Santa Claus to visit all the cities and return back. We will neglect the time at which he lays out all the gifts!

Input
The first line of the input contains two integers N and M (1 <= N <= 12, 0 <= M <=5). The following N lines contain the coordinates of cities (X_i, Y_i). Then there are M lines with accelerator coordinates (P_i, Q_i). All coordinates are different and there is no (0, 0).

Imprint
Print the answer to the problem, with an accuracy of at least 6 decimal places.

Examples

#	Input	Output	Note
1	2 1 1 1 0 1 10	2 1 1 1 0 1 10	Here is one of the best ways to distribute all the gifts Move distance 1 from the origin to accelerator 1 at speed 1, spending time 1. Move distance 1 from accelerator 1 to city 1 at speed 2 in time 0.5. Travel distance 1 from city 1 to city 2 at speed 2, taking time 0.5. Travel distance 1 from city 2 to origin at speed 2 in time 0.5.
2	2 1 1 1 0 1 1000	3.4142135624	Here is one of the best ways to distribute all the gifts Travel distance 1.41... from origin to city 1 at speed 1, spending time 1.41.... Travel distance 1 from city 1 to city 2 at speed 1, spending time 1. Travel distance 1 from city 2 to the origin at speed 1, spending time 1.
3	1 2 4 4 10 0 1	4.3713203436	Here is one of the best ways to distribute all the gifts Move distance 1 from the origin to accelerator 1 at speed 1, spending time 1. Move distance 1.41... from accelerator 1 to accelerator 2 at speed 2, spending time 0.707.... Move distance 5 from accelerator 2 to city 1 at speed 4 in time 1.25. Travel distance 5.65... from city 1 to origin at speed 4, spending time 1.41....