# catalogue

Concept of graph

Storage mode of graph

Title: adjacency matrix representation of Graphs

Title: the forward star of a graph represents 1

ergodic

Depth first search

Shortest path algorithm

Dijkstra algorithm

Title: Party

Bellman Ford algorithm

SPFA algorithm

Title: making money

Floyd algorithm

minimum spanning tree

Kruskal algorithm

Title: busy city

Title: extended complete graph

Prim algorithm

Title: Dark Castle

Concluding remarks

# Concept of graph

1. Definition of graph
Graph G is composed of vertex set V and edge set E, which is marked as g = (V, e). V cannot be empty, e can be empty, and the number of vertices is also called the order of graph G.
2. Directed graph
When E is a finite set of directed edges (arcs), graph G is a directed graph, arcs are ordered pairs of vertices, marked as < v, w >, v and W are vertices, and arcs point from v (arc tail) to w (arc head)
3. Undirected graph
When E is a finite set of undirected edges, graph G is an undirected graph. The edge (v,w) can be from V to w or from w to v
4. Simple graph (data structure only discusses simple graph) is opposite to multiple graph
① there are no duplicate edges
② there is no edge from vertex to itself
5. Complete graph (there are edges between any two points)
For an undirected graph, there are n*(n-1)/2 edges, which is called an undirected complete graph
For a directed graph, there are n*(n-1) arcs, which is called a directed complete graph
6. Subgraph
If the vertices and edges of graph G1 are included in graph G2, G1 is said to be a subgraph of G2
7. Connected, connected graph and connected component (undirected graph)
In an undirected graph, if there is a path from vertex v to vertex w, then V and w are connected.
If any two vertices in graph G are connected, graph G is called connected graph, otherwise it is called unconnected graph.
A polar connected subgraph in an undirected graph is called a connected component
If a graph has n vertices and the number of edges is less than n-1, the graph must be unconnected.
8. Strongly connected graph, strongly connected component (directed graph)
In a directed graph, if there are paths from vertex v to W and from w to V, the two vertices are said to be strongly connected, and the graph is said to be strongly connected.
The maximal strongly connected subgraph in a directed graph is called the strongly connected component of a directed graph.
9. Degree of vertex
The degree of a vertex, the number of edges with that vertex as an endpoint
In an undirected graph, the sum of the degrees of all vertices is equal to twice the number of edges, because each edge is connected to two vertices
In a directed graph, the degree of vertex v is divided into outgoing degree and incoming degree. The incoming degree is the number of arcs pointing to vertex v, and the outgoing degree is the number of arcs starting from vertex v. The sum of in and out degrees of all vertices of a directed graph is equal and equal to the number of edges. Because every directed edge has a starting point and an ending point
10. Edge weight and net
Each edge in the graph can be marked with a value with some meaning, which is called the weight of the edge. This kind of graph with weight on the edge is called the graph with total weight, also known as net
11. Dense graph and sparse graph
The two are relative. Generally, when graph G satisfies | e | < | V | log | V |, it can be regarded as a sparse graph
12. Path, path length, loop
A path from vertex v to vertex p refers to the sequence of vertices. Of course, the associated edges can also be understood as the constituent elements of the path. The number of edges on a path is called the path length. The same path between the first vertex and the last vertex is called a loop or ring.
If a graph has n vertices and more than n-1 edges, the graph must have rings.
13. Simple path
In the path sequence, the path whose vertices do not appear repeatedly is called a simple path. A circuit in which other vertices do not reappear except the first and last vertices is called a simple circuit

# Storage mode of graph

A[i][j]=1, which means there is a path between vertex i and vertex j, < I, j > is an edge in E, otherwise it is 0. The adjacency matrix of an undirected graph is generally a symmetric matrix.

### Title: adjacency matrix representation of Graphs

Title Description

Input the information of an undirected graph, and output the adjacency matrix of the graph, the number of vertices directly connected to vertex t and the adjacency points.

Input description

There are two integers in the first row, N and K. n represents a total of n vertices and K represents a total of k edges
In the next 2~k+1 lines, each line has three integers x, y and z, respectively representing that X and y are connected, and the weight is z (not 0)
Enter a t on line k+2.

Output description

The first n rows output the information of the adjacency matrix. (the number in the adjacency table represents the weight. If it is not connected, the weight is 0)
Line n+1 outputs the number of vertices directly connected to vertex t and all adjacent points.

Sample

input

```5 3
1 3 9
2 4 5
3 5 3
3```

output

```0 0 9 0 0
0 0 0 5 0
9 0 0 0 3
0 5 0 0 0
0 0 3 0 0
2 1 5```
```#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=55;
int a[MAXN][MAXN],k[MAXN*MAXN];
int main(){
int n,m,t;
scanf("%d %de",&n,&m);
for(int i=1;i<=m;i++){
int x,y,num;
scanf("%d %d %d",&x,&y,&num);
a[x][y]=num;
a[y][x]=num;
}
scanf("%d",&t);
int ans=0;
for(int i=1;i<=n;i++){
if(a[i][t]!=0){
ans++;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
printf("%d ",a[i][j]);
}
printf("\n");
}
printf("%d ",ans);
for(int i=1;i<=n;i++){
if(a[i][t]!=0){
printf("%d ",i);
}
}
return 0;
}```

When a graph is sparse, the adjacency matrix method obviously wastes a lot of storage space, and the adjacency table method of graph combines sequential storage and chain storage methods to greatly reduce this unnecessary waste. The so-called adjacency table refers to establishing a single chain table for each vertex v in graph G. the nodes in the ith single chain table represent the edges attached to vertex v (for a directed graph, it is an arc with vertex v as the tail). This single chain table is called the edge table of vertex v (for a directed graph, it is called the out edge table).

### Title: the forward star of a graph represents 1

Title Description

Given the information of a directed graph, the adjacent points of each node are output in the way of forward interpolation.

Input description

In the first row, there are two integers n, m (1 < = n, m < = 10 ^ 5). N represents the number of nodes in the graph, and M represents the number of edges in the graph.

Next m lines, two integers x and Y in each line, indicating that x can reach y directly.

Output description

The output occupies n lines in total. The beginning of line I is node i and a colon ":", followed by all adjacent contact numbers of I. each number is separated by a space. If I has no adjacent point, zero is output.

Sample

input

```5 4
1 2
1 3
1 4
2 5```

output

```1: 4 3 2
2: 5
3: zero
4: zero
5: zero```
```#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXNM=100005;
int first[MAXNM],tot=-1;
struct node{
int ver;
int nxt;
}a[MAXNM];
a[++tot].ver=v;
a[tot].nxt=first[u];
first[u]=tot;
}
int main(){
memset(first,-1,sizeof(first));
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d %d",&x,&y);
}
for(int i=1;i<=n;i++){
printf("%d: ",i);
if(first[i]==EOF){
printf("zero\n");
continue;
}
for(int j=first[i];j!=-1;j=a[j].nxt){
printf("%d ",a[j].ver);
}
printf("\n");
}
return 0;
}```

# ergodic

## Depth first search

Title Description

Depth first search traversal is similar to the root first traversal of a tree, which is a generalization of the root first traversal of a tree. The process is as follows: assuming that the initial state is that all vertices in the graph have not been accessed, the depth first search can start from a vertex v in the graph, access this vertex, and then traverse the graph in depth first from the unreachable adjacent points of V until all vertices connected with V in the graph are accessed; If there are still vertices in the graph that have not been accessed at this time, select another vertex in the graph that has not been accessed as the starting point, and repeat the above process until all vertices in the graph are accessed.

In this problem, read in the adjacency matrix (i.e. array representation) of an undirected graph, establish an undirected graph, traverse all vertices according to the algorithm described above, and output the order of traversing vertices.

Input description

The first line of input contains a positive integer n, indicating that there are n vertices in the graph. Where n does not exceed 50.

In the next N lines, each line has n integers 0 or 1 separated by spaces. For the jth 0 or 1 in line i, 1 indicates that the ith vertex is directly connected with the jth vertex, and 0 indicates that there is no direct connection. When i and j are equal, ensure that the corresponding integer is 0.

The input ensures that the adjacency matrix is a symmetric matrix, that is, the input graph must be undirected.

Output description

There is only one line, containing n integers, which indicates the order of accessing vertices of the whole graph according to the depth first traversal algorithm in the title description. Output a space after each integer, and pay attention to the line wrap at the end of the line.

Sample

input

```4
0 1 0 1
1 0 0 0
0 0 0 1
1 0 1 0```

output

`0 1 3 2`

We only need to traverse one subscript of the graph. If there are nodes, we will continue to search.

```#include<iostream>
#include<cstdio>
using namespace std;
const int N=50;
int n,g[N][N];
bool vis[N];
void dfs(int step){
vis[step]=true;
printf("%d ",step);
for(int i=0;i<n;i++){
if(g[step][i]!=0&&!vis[i]) dfs(i);
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&g[i][j]);
}
}
for(int i=0;i<n;i++){
if(!vis[i]) dfs(i);
}
return 0;
}```

Title Description

Breadth first search traversal is similar to the hierarchical traversal of a tree. The process is as follows: suppose that starting from a vertex 0 in the graph, after accessing 0, each adjacent point that has not been accessed is accessed in turn from small to large, and then their adjacent points are accessed in turn from these adjacent points, and the "adjacent point of the first accessed vertex" is accessed before the "adjacent point of the later accessed vertex", Read in the adjacency matrix (i.e. array representation) of an undirected graph, establish an undirected graph, and output the order of traversing vertices according to the calculation in the above description.

Note: if you can't reach other points after one round of traversal, the program ends.

Input description

The first line of input contains a positive integer n, indicating that there are n vertices in the graph. Where n does not exceed 50.

In the next N lines, each line has n integers 0 or 1 separated by spaces. For the jth 0 or 1 in line i, 1 indicates that the ith vertex is directly connected with the jth vertex, and 0 indicates that there is no direct connection. When i and j are equal, ensure that the corresponding integer is 0.

The input ensures that the adjacency matrix is a symmetric matrix, that is, the input graph must be undirected.

Output description

There is only one line, including n integers, which indicates the order of accessing vertices of the whole graph according to the breadth first traversal algorithm in the title description. Output a space after each integer

Sample

input

```4
0 0 0 1
0 0 1 1
0 1 0 1
1 1 1 0```

output

`0 3 1 2`

Like the idea of deep search, just add a queue

```#include<iostream>
#include<cstdio>
using namespace std;
const int N=55;
int a[N][N];
bool v[N]={0};
int q[N],front,rear;
int n;
void bfs(int x){
q[rear++]=x;
v[x]=1;
while(rear!=front){
int t=q[front++];
printf("%d ",t);
for(int i=0;i<n;i++){
if(a[t][i]!=0&&!v[i]){
q[rear++]=i;
v[i]=1;
}
}
}
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
bfs(0);
return 0;
}```

# Shortest path algorithm

## Dijkstra algorithm

Here is the code to find the 1-n shortest path

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2005;
const int M=10005;
int n,m;
bool fla[M],vis[M];
int A[N][N],dist[M];
void dijkstra(int root){
memset(dist,0x3f3f3f3f,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[root]=0;
for(int i=1;i<n;i++){
int x=-1;
for(int j=1;j<=n;j++)
if(!vis[j]&&(x==-1||dist[j]<dist[x])) x=j;
vis[x]=true;
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],dist[x]+A[x][j]);
}
}
signed main(){
int x,y,z,root;
memset(A,0x3f,sizeof(A));
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z);
A[x][y]=min(A[x][y],z);
A[y][x]=min(A[y][x],z);

}
dijkstra(1);
printf("%d",dist[n]);
return 0;
}```

### Title: Party

Title Description

Little S wants to go to a party at his classmate'S home from somewhere, but he has to go back and forth. He wants to keep the time as short as possible. But he also wants to know the shortest and longest time from different points, and the task is up to you.

Input description

Three positive integers n, m and k in the first line (n is the number of nodes, M is the number of directed edges, and k is the number of places to attend the party) (1 ≤ n ≤ 1000, 1 ≤ m ≤ 100000)

The second line m+1 line, 3 integers in each line, x,y, w represents the time it takes W from X to y (1 ≤ w ≤ 100)

Input data to ensure that the party is connected to other points

Output description

Output the longest time in the shortest time from different nodes.

Sample

input

```4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3```

output

`10`

Tip: there are multiple edges

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005;
const int INF=0x3f3f3f3f;
int n,m,root,sum=0;
int dist1[N],dist2[N];
int tu1[N][N],tu2[N][N];
bool vis[N];
void dijkstra1(){
memset(dist1,INF,sizeof(dist1));
memset(vis,0,sizeof(vis));
dist1[root]=0;
for(int i=1;i<n;i++){
int num=-1;
for(int j=1;j<=n;j++)
if(vis[j]==0&&(num==-1||dist1[j]<dist1[num])) num=j;
vis[num]=true;
for(int j=1;j<=n;j++){
dist1[j]=min(dist1[j],dist1[num]+tu1[num][j]);
}
}
}
void dijkstra2(){
memset(dist2,INF,sizeof(dist1));
memset(vis,0,sizeof(vis));
dist2[root]=0;
for(int i=1;i<n;i++){
int num=-1;
for(int j=1;j<=n;j++)
if(vis[j]==0&&(num==-1||dist2[j]<dist2[num])) num=j;
vis[num]=true;
for(int j=1;j<=n;j++){
dist2[j]=min(dist2[j],dist2[num]+tu2[num][j]);
}
}
}
signed main(){
memset(tu1,INF,sizeof(tu1));
memset(tu2,INF,sizeof(tu2));
for(int i=0;i<N;i++){
tu1[i][i]=tu2[i][i]=0;
}
scanf("%d %d %d",&n,&m,&root);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
tu1[x][y]=tu2[y][x]=min(tu1[x][y],z);
}
dijkstra1();
dijkstra2();
for(int i=1;i<=n;i++){
sum=max(sum,dist1[i]+dist2[i]);
}
printf("%d\n",sum);
return 0;
}```

## Bellman Ford algorithm

Here is the code to find the 1-n shortest path.

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
const int INF=0x3f3f3f3f;
int n,m;
int dist[N],pre[N];
struct node{
int x;
int y;
int z;
}tu[N];
void bellman_ford(int root){
memset(dist,INF,sizeof(dist));
memset(pre,0,sizeof(pre));
dist[root]=0;
for(int i=1;i<n;i++){
bool flag=false;
for(int j=1;j<=2*m;j++){
node tmp=tu[j];
if(dist[tmp.y]>dist[tmp.x]+tmp.z){
dist[tmp.y]=dist[tmp.x]+tmp.z;
flag=true;
}
if(dist[tmp.x]>dist[tmp.y]+tmp.z){
dist[tmp.x]=dist[tmp.y]+tmp.z;
flag=true;
}
}
if(!flag) break;
}
}
signed main(){
while(1){
scanf("%d %d",&n,&m);
if(n==0&&m==0) return 0;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&tu[i].x,&tu[i].y,&tu[i].z);
}
bellman_ford(1);
printf("%d\n",dist[n]);
}
return 0;
}```

## SPFA algorithm

Here is the code to find the 1-n shortest path.

```#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5;
const int INF=0x3f3f3f3f;
queue<int>q;
struct node{
int ver;
int nxt;
int edge;
}tu[N];
int n,m;
int dist[N];
bool vis[N];
tu[++tot].ver=y;
tu[tot].edge=z;
}
void spfa(int root){
memset(dist,INF,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[root]=0;
vis[root]=1;
q.push(root);
while(q.size()){
int x=q.front();
q.pop();
vis[x]=0;
int y=tu[i].ver,z=tu[i].edge;
if(dist[y]>dist[x]+z){
dist[y]=dist[x]+z;
if(!vis[y]){
q.push(y);
vis[y]=true;
}
}
}
}
}
signed main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
}
spfa(1);
if(dist[n]==INF) printf("impossible");
else printf("%d",dist[n]);
return 0;
}```

### Title: making money

Title Description

Kdy now decides to travel around China and make some money by the way. Kdy can only earn D yuan at most in one city, and then he can choose to retire, that is, stop making money, or work in other cities. Of course, he can work elsewhere for a while and then return to his original city to earn D yuan. There is no limit to the number of such round trips. There are P one-way paths between cities, with a total of C cities, numbered from 1 to C. Path i is from City Ai to city Bi, and there is no cost in walking on the path. Kdy can also fly from one city to another. There are F one-way routes in total, and the i route flies from City Ji to another city Ki at the cost of Ti yuan. If kdy has no cash on him, he can use the money he earns to pay for the ticket. Kdy can start making money from any city and choose to retire at any time and in any city. Now kdy wants to know how much money kdy can make if there are no restrictions on working hours? If there is no limit to the money you earn, output orz.

Input description

First line, 4 positive integers separated by spaces, D, P, C, F. The second line to line P+1, line i+1 contains two integers separated by spaces, representing a one-way path from City Ai to city Bi. The next f line, with three positive integers separated by spaces in each line, represents a one-way route from City Ji to city Ki, and the cost is Ti.

Output description

If there is no limit to how much money kdy can earn, output orz. If there is a limit, the maximum amount of money kdy can earn under a given rule is output.

Sample

input

```100 3 5 2
1 5
2 3
1 4
5 2 150
2 5 120```

output

`250`

Queue simulation

```#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5;
const int INF=0x3f3f3f3f;
queue<int>q;
struct node{
int ver;
int nxt;
int edge;
}tu[N];
int mon,p,n,f,ans;
int cnt[N];
int dist[N];
bool vis[N];
tu[++tot].ver=y;
tu[tot].edge=z;
}
bool spfa(){
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++){
dist[i]=mon;
vis[i]=1;
q.push(i);
}
while(q.size()){
int x=q.front();
q.pop();
vis[x]=0;
int y=tu[i].ver,z=tu[i].edge;
if(dist[y]<dist[x]+mon-z){
dist[y]=dist[x]+mon-z;
cnt[y]=cnt[x]+1;
if(cnt[y]>=n) return true;
if(!vis[y]){
q.push(y);
vis[y]=true;
}
}
}
}
return false;
}
signed main(){
cin>>mon>>p>>n>>f;
for(int i=1;i<=p;i++){
int x,y;
cin>>x>>y;
}
for(int i=1;i<=f;i++){
int x,y,z;
cin>>x>>y>>z;
}
if(spfa()) printf("orz\n");
else{
for(int i=1;i<=n;i++) ans=max(ans,dist[i]);
printf("%d\n",ans);
}
return 0;
}```

## Floyd algorithm

Here is the code to find the 1-n shortest path.

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=205;
const int INF=0x3f3f3f3f;
int n,m;
int g[N][N];
void init(int num){
for(int i=1;i<=num;i++){
for(int j=1;j<=num;j++){
if(i==j) g[i][j]=0;
else g[i][j]=INF;
}
}
}
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
}
signed main(){
cin>>n>>m;
init(n);
while(m--){
int x,y,z;
cin>>x>>y>>z;
g[x][y]=min(g[x][y],z);
}
floyd();
if(g[n]>INF/2) printf("impossible\n");
else printf("%d\n",g[n]);
return 0;
}```

# minimum spanning tree

## Kruskal algorithm

The following is the code for finding the minimum spanning tree.

```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e3+10;
const int M=2e5+10;
const int INF=0x3f3f3f3f;
int n,m;
int father[N];
struct node{
int x;
int y;
int z;
}edge[N];
void init(int num){
for(int i=1;i<=num;i++){
father[i]=i;
}
}
bool cmp(node xx,node yy){
return xx.z<yy.z;
}
int fd(int num){
if(father[num]==num) return num;
int root=fd(father[num]);
return father[num]=root;
}
int a=fd(x),b=fd(y);
if(a==b) return;
father[a]=b;
return;
}
int kruskal(){
int ans=0,cnt=0;
sort(edge+1,edge+1+m,cmp);
for(int i=1;i<=m;i++){
int fx=fd(edge[i].x);
int fy=fd(edge[i].y);
if(fx==fy) continue;
cnt++;
ans+=edge[i].z;
}
if(cnt==n-1) return ans;
else return INF;
}
signed main(){
scanf("%d %d",&n,&m);
init(n);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].z);
}
int ans=kruskal();
if(ans==INF) printf("orz\n");
else printf("%d\n",ans);
return 0;
}```

### Title: busy city

Title Description

Input description

The first line has two integers n,m indicates that there are n intersections and M roads in the city. Next, line m is the description of each road. U, v and C represent the intersection. There are roads connected between u and v, and the score is C. (1≤n≤300，1≤c≤10000).

Output description

Two integers, s, max, indicate how many roads you have selected, and what is the score of the road with the largest score.

Sample

input

```4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8```

output

```3 6
```
```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=305;
const int M=2e5+10;
const int INF=0x3f3f3f3f;
int n,m,last;
int father[N];
struct node{
int x;
int y;
int z;
}edge[M];
void init(int num){
for(int i=1;i<=num;i++){
father[i]=i;
}
}
bool cmp(node xx,node yy){
return xx.z<yy.z;
}
int fd(int num){
if(father[num]==num) return num;
int root=fd(father[num]);
return father[num]=root;
}
int a=fd(x),b=fd(y);
if(a==b) return;
father[a]=b;
return;
}
int kruskal(){
int sum=0,cnt=0;
sort(edge+1,edge+1+m,cmp);
for(int i=1;i<=m;i++){
int fx=fd(edge[i].x);
int fy=fd(edge[i].y);
if(fx==fy) continue;
cnt++;
sum+=edge[i].z;
last=edge[i].z;
}
if(cnt==n-1) return sum;
}
signed main(){
scanf("%d %d",&n,&m);
init(n);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].z);
}
int ans=kruskal();
if(ans==INF) printf("orz\n");
else printf("%d %d\n",n-1,last);
return 0;
}```

### Title: extended complete graph

Title Description

Given a tree with N nodes, it is required to add several edges, expand the tree into a complete graph, and satisfy that the only minimum spanning tree of the graph is still the tree. Find the minimum sum of the weights of the increased edges. Note: all edge weights in the tree are integers, and all newly added edge weights must also be integers.

Input description

The first row contains the integer t, which represents a total of t groups of test data. For each set of test data, the first row contains the integer N. Next, in line N-1, there are three integers x, Y and Z in each line, indicating that there is an edge between node X and node Y, with a length of Z.
1≤N≤6000
1≤Z≤100

Output description

Each group of data outputs an integer representing the minimum value of the sum of weights. One line for each result.

Sample

input

```2
3
1 2 2
1 3 3
4
1 2 3
2 3 4
3 4 5 ```

output

```4
17```
```#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6e3+10;
const int M=2e5+10;
const int INF=0x3f3f3f3f;
int n,m,last;
int father[M],size[M];
struct node{
int x;
int y;
int z;
}edge[M];
void init(int num){
for(int i=1;i<=num;i++){
father[i]=i;
size[i]=1;
}
}
bool cmp(node xx,node yy){
return xx.z<yy.z;
}
int fd(int num){
if(father[num]==num) return num;
int root=fd(father[num]);
return father[num]=root;
}
int a=fd(x),b=fd(y);
if(a==b) return;
father[a]=b;
return;
}
int kruskal(){
int ans=0,cnt=0;
sort(edge+1,edge+1+m,cmp);
for(int i=1;i<=m;i++){
int fx=fd(edge[i].x);
int fy=fd(edge[i].y);
if(fx==fy) continue;
ans+=(long long)(size[fx]*size[fy]-1)*(edge[i].z+1);
size[fx]+=size[fy];
}
return ans;
}
signed main(){
int tmp;
scanf("%d",&tmp);
while(tmp--){
scanf("%d",&n);
init(n);
m=n-1;
for(int i=1;i<=m;i++){
scanf("%d %d %d",&edge[i].x,&edge[i].y,&edge[i].z);
}
printf("%d\n",kruskal());
}
return 0;
}```

## Prim algorithm

The following is the code for finding the minimum spanning tree.

```#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3005;
const int INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool vis[N];
int prim(int s){
int ans=0;
memset(dist,INF,sizeof(dist));
dist[s]=0;
for(int i=1;i<=n;i++){
int x=-1;
for(int j=1;j<=n;j++){
if(!vis[j]&&(x==-1||dist[j]<dist[x])){
x=j;
}
}
vis[x]=true;
for(int j=1;j<=n;j++){
if(!vis[j]){
dist[j]=min(dist[j],g[x][j]);
}
}
}
for(int i=1;i<=n;i++){
if(dist[i]==INF) return INF;
else ans+=dist[i];
}
return ans;
}
signed main(){
memset(g,INF,sizeof(g));
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
g[x][y]=g[y][x]=min(g[x][y],z);
}
int ans=prim(1);
if(ans==INF) printf("orz\n");
else printf("%d\n",ans);;
return 0;
}```

### Title: Dark Castle

Title Description

After successfully breaking through Lord lsp's defense line, lqr the party came to the bottom of Lord lsp's castle. After Lord lsp blackened, although he has powerful super ability and can make buildings with his mind, his IQ level has not increased much. Now lqr it is clear that the dark castle has N rooms, M two-way channels that can be made, and the length of each channel. lqr is well aware of Lord lsp's idea. In order to avoid thinking about the shortest path between two rooms every time, Lord lsp will build the castle into a tree. However, in order to improve its movement efficiency as much as possible, Lord lsp will make the castle meet the following conditions: let D[i] be the shortest path length between room I and room 1 if all channels are built; S[i] is the path length between room I and room 1 in the actually built tree castle; It is required that S[i]=D[i] holds for all integers I. In order to defeat Lord lsp, lqr wants to know how many different castle building schemes there are. You need to output the result after the answer is modeled on 2 ^ 31 – 1.

Input description

The first line has two integers N and M. After that, there are three integers x, Y and l in line M, indicating that a channel with length L between X and Y can be built.
2≤N≤1000

N−1≤M≤N(N−1)/2
1≤L≤100

Output description

An integer that represents the result after the answer modulo 2 ^ 31 – 1.

Sample

input

```3 3
1 2 2
1 3 1
2 3 1```

output

`2`
```#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define P 2147483647
#define int long long
const int N=3005;
const int INF=0x3f3f3f3f;
int n,m;
int sum[N];
int g[N][N];
int dist[N];
bool vis[N];
int prim(int root){
int ans=1;
memset(dist,INF,sizeof(dist));
memset(vis,0,sizeof(vis));
dist[root]=0;
sum[root]=1;
for(int i=1;i<n;i++){
int x=0;
for(int j=1;j<=n;j++){
if(!vis[j]&&(x==0||dist[j]<dist[x])){
x=j;
}
}
vis[x]=true;
for(int y=1;y<=n;y++){
if(!vis[y]){
if(dist[y]==dist[x]+g[x][y]) sum[y]++;
else if(dist[y]>dist[x]+g[x][y]){
dist[y]=dist[x]+g[x][y];
sum[y]=1;
}
}
}
}
for(int i=1;i<=n;i++){
ans=(int)(ans*sum[i])%P;
}
return ans;
}
signed main(){
memset(g,INF,sizeof(g));
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
g[x][y]=g[y][x]=min(g[x][y],z);
}
int ans=prim(1);
printf("%d\n",ans);
return 0;
}```

# Concluding remarks

Thanks for the company of fans, I will continue to work hard!! [Ollie gives]

Keywords: Algorithm data structure Graph Theory

Added by siwelis on Fri, 11 Feb 2022 11:00:02 +0200