catalogue
Title: adjacency matrix representation of Graphs
Title: the forward star of a graph represents 1
Title: extended complete graph
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
adjacency matrix
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;
}Adjacency table
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];
void add(int u,int v){
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);
add(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;
}Breadth first search
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;
int tot=1,head[N];
struct node{
int ver;
int nxt;
int edge;
}tu[N];
int n,m;
int dist[N];
bool vis[N];
void add(int x,int y,int z){
tu[++tot].ver=y;
tu[tot].edge=z;
tu[tot].nxt=head[x];
head[x]=tot;
}
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;
for(int i=head[x];~i;i=tu[i].nxt){
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(){
memset(head,-1,sizeof(head));
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
add(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;
int tot=1,head[N];
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];
void add(int x,int y,int z){
tu[++tot].ver=y;
tu[tot].edge=z;
tu[tot].nxt=head[x];
head[x]=tot;
}
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;
for(int i=head[x];~i;i=tu[i].nxt){
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(){
memset(head,-1,sizeof(head));
cin>>mon>>p>>n>>f;
for(int i=1;i<=p;i++){
int x,y;
cin>>x>>y;
add(x,y,0);
}
for(int i=1;i<=f;i++){
int x,y,z;
cin>>x>>y>>z;
add(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[1][n]>INF/2) printf("impossible\n");
else printf("%d\n",g[1][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;
}
void link(int x,int y){
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;
link(fx,fy);
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
City C is a very busy metropolis. The roads in the city are very crowded, so the mayor decided to transform the roads. The roads in City C are distributed in this way: there are n intersections in the city, some intersections are connected by roads, and there is at most one road between the two intersections. These roads are two-way and connect all intersections directly or indirectly. Each road has a score. The smaller the score, the busier the road is and the more reconstruction is needed. However, the capital of the municipal government is limited, and the mayor hopes that the fewer roads to be reconstructed, the better, so he puts forward the following requirements: 1. The reconstructed roads can connect all intersections directly or indirectly. 1. Meet the requirements of road reconstruction as little as possible. 3. Under the condition of meeting requirements 1 and 2, the maximum score of the reconstructed roads shall be as small as possible. As a member of the Municipal Planning Bureau, you should make the best decision and choose which roads should be built.
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;
}
void link(int x,int y){
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;
link(fx,fy);
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;
}
void link(int x,int y){
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);
link(fy,fx);
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]