পোস্টগুলি

Dijkstra's shortest path algorithm-2

 // A C++ program for Dijkstra's single source shortest path algorithm. // The program is for adjacency matrix representation of the graph #include <iostream> using namespace std; #include <limits.h> // Number of vertices in the graph #define V 9 // A utility function to find the vertex with minimum distance value, from // the set of vertices not yet included in shortest path tree int minDistance(int dist[], bool sptSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } // A utility function to print the constructed distance array void printSolution(int dist[]) { cout <<"Vertex \t Distance from Source" << endl; for (int i = 0; i < V; i++) cout << i << " \t\t"<<dist[i]<< endl; } // Function that implements Dijkstra's single source shortest path alg

Kruskal’s Algorithm-2

 // Simple C++ implementation for Kruskal's // algorithm //https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ #include <bits/stdc++.h> using namespace std; #define V 5 int parent[V]; // Find set of vertex i int find(int i) { while (parent[i] != i) i = parent[i]; return i; } // Does union of i and j. It returns // false if i and j are already in same // set. void union1(int i, int j) { int a = find(i); int b = find(j); parent[a] = b; } // Finds MST using Kruskal's algorithm void kruskalMST(int cost[][V]) { int mincost = 0; // Cost of min MST. // Initialize sets of disjoint sets. for (int i = 0; i < V; i++) parent[i] = i; // Include minimum weight edges one by one int edge_count = 0; while (edge_count < V - 1) { int min = INT_MAX, a = -1, b = -1; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (find(i) != find(j) && cost[i][j] < min) { min = cost[i][j];

prime algorithm-2

 // A C++ program for Prim's Minimum // Spanning Tree (MST) algorithm. The program is // for adjacency matrix representation of the graph #include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define V 5 // A utility function to find the vertex with // minimum key value, from the set of vertices // not yet included in MST int minKey(int key[], bool mstSet[]) { // Initialize min value int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (mstSet[v] == false && key[v] < min) min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] void printMST(int parent[], int graph[V][V]) { cout<<"Edge \tWeight\n"; for (int i = 1; i < V; i++) cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n"; } // Function to construct and print MST for // a graph represented using

Prime Algorithm

 #include<stdio.h> int a,b,u,v,n,i,j,ne=1; int visited[10]= {0},min,mincost=0,cost[10][10]; int main() {     //clrscr();     printf("\nEnter the number of nodes:");     scanf("%d",&n);     printf("\nEnter the adjacency matrix:\n");     for(i=1; i<=n; i++)         for(j=1; j<=n; j++)         {             scanf("%d",&cost[i][j]);             if(cost[i][j]==0)                 cost[i][j]=999;             printf("i=%d j=%d cost=%d\n",i,j,cost[i][j]);         }     visited[1]=1;     printf("\n");     while(ne < n)     {         for(i=1,min=999; i<=n; i++)         {             for(j=1; j<=n; j++)             {                 printf("iiii=%d jjjj=%d cost=%d\n",i,j,cost[i][j]);                 printf("%d\n",min);                 if(cost[i][j]< min)                     if(visited[i]!=0)                     {                         min=cost[i][j];                         a=u=i;    

kruskal algorithm

 #include<bits/stdc++.h> using namespace std; int main() {     long long i,j,n,k,temp,ar[100]= {},a[100],b[100],x[100],y[100],aa;     cin>>n;     k=0;     for(i=0; i<n; i++)     {         for(j=0; j<n; j++)         {             cout<<i+1<<" "<<j+1<<"=";             cin>>aa;             ar[k]=aa;             if(aa==0)                 ar[k]=999;             a[k]=i;             b[k]=j;             k++;             cout<<endl;         }     }     for(i=0; i<k; i++)     {         for(j=i+1; j<k; j++)         {             if(ar[i]>ar[j])             {                 temp=ar[i];                 ar[i]=ar[j];                 ar[j]=temp;                 temp=a[i];                 a[i]=a[j];                 a[j]=temp;                 temp=b[i];                 b[i]=b[j];                 b[j]=temp;             }         }     }     for(i=0; i<100; i++)     {         x[i]=0;         y[i]=0;     }     for(i=0; i

Job Sequencing Problem

 #include<bits/stdc++.h> using namespace std; int main() {     long long p[100],d[100],i,n,temp,j,x[100];     cin>>n;     for(i=0; i<n; i++)         cin>>p[i]>>d[i];     for(i=0; i<n; i++)     {         for(j=i+1; j<n; j++)         {             if(p[i]<p[j])             {                 temp=p[i];                 p[i]=p[j];                 p[j]=temp;                 temp=d[i];                 d[i]=d[j];                 d[j]=temp;             }         }     }     for(i=0; i<100; i++)         x[i]=0;     for(i=0; i<n; i++)     {             j=i;         while(j>=0)         {             if(x[d[j]]==0)             {                 x[d[j]]=p[j];                 cout<<d[j]<<"        "<<x[d[j]]<<"    "<<j<<endl;             }             j--;         }     } long long sum=0;     for(i=0;i<100;i++)         sum=sum+x[i];         cout<<sum<<endl; }

lexicographical (alphabetical) order

B. K-th Beautiful String time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output For the given integer  n n  ( n > 2 n > 2 ) let's write down all the strings of length  n n  which contain  n − 2 n − 2  letters ' a ' and two letters ' b ' in  lexicographical  (alphabetical) order. Recall that the string  s s  of length  n n  is lexicographically less than string  t t  of length  n n , if there exists such  i i  ( 1 ≤ i ≤ n 1 ≤ i ≤ n ), that  s i < t i s i < t i , and for any  j j  ( 1 ≤ j < i 1 ≤ j < i )  s j = t j s j = t j . The lexicographic comparison of strings is implemented by the operator  <  in modern programming languages. For example, if  n = 5 n = 5  the strings are (the order does matter): aaabb aabab aabba abaab ababa abbaa baaab baaba babaa bbaaa It is easy to show that such a list of strings will contain exactly  n ⋅ ( n − 1 ) 2 n ⋅ ( n