[go: up one dir, main page]
Scribd
Upload
152 views9 pages

Experiment No - 3: AIM: Calculate The Difference Between Maximum Sum and Minimum Sum of N-M Elements of

The document describes an experiment to calculate the difference between the maximum sum and minimum sum of N-M elements of a given array. It provides the source code, which takes input of test cases t, size of array N, and number of elements to exclude M. It sorts the array, calculates the sums of first N-M and last N-M elements, and outputs the absolute difference between the sums.

Uploaded by

rohit kashyap
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
152 views9 pages

Experiment No - 3: AIM: Calculate The Difference Between Maximum Sum and Minimum Sum of N-M Elements of

The document describes an experiment to calculate the difference between the maximum sum and minimum sum of N-M elements of a given array. It provides the source code, which takes input of test cases t, size of array N, and number of elements to exclude M. It sorts the array, calculates the sums of first N-M and last N-M elements, and outputs the absolute difference between the sums.

Uploaded by

rohit kashyap
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 9

EXPERIMENT NO - 3

AIM: Calculate the difference between maximum sum and minimum sum of N-M elements of
the given array.

SOURCE CODE:
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,M,N,A[1000];
cin>>t;
for(int i=0;i<t;i++)
{
cin>>N;
cin>>M;
for(int j=0;j<N;j++)
cin>>A[j];
sort(A,A+N);
int sum1 = 0,sum2 = 0;
for(int k=0,l=M;k<N-M-1,l<N;k++,l++)
{
sum1 = sum1+A[k];
sum2 = sum2+A[l];
}
cout<<abs(sum1-sum2)<<endl;
}
return 0;
}
OUTPUT:
EXPERIMENT NO -4

Aim: Perform Krushkal Minimum Spanning Tree.


Source Code:
#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
vector<int> p(3001),rnk(3001,1);
int find(int a){
return p[a]==a?a:p[a]=find(p[a]);
}
bool same(int a,int b){
return find(a)==find(b);
}
void merge(int a,int b){
/*if(!same(a,b))*/{
if(rnk[find(a)]>rnk[find(b)]){
// num[find(a)]+=num[find(b)];
p[find(b)]=find(a);
}
else {
// num[find(b)]+=num[find(a)];
p[find(a)]=find(b);
}
if(rnk[find(a)]==rnk[find(b)])
rnk[find(b)]++;
}
}
int main(){
int n,e;
cin>>n>>e;
for(int i=1;i<=n;i++)
p[i]=i;
vector<vector<int> > a;
for(int i=0;i<e;i++){
int x,y,w;
cin>>x>>y>>w;
a.push_back({w,x,y});
}
sort(a.begin(),a.end(),[](const vector<int> &l,const vector<int> &r){
if(l[0]<r[0])
return true;
if(l[0]==r[0])
return l[1]+l[2]<r[1]+r[2];
return false;
});
int sum=0;
for(int i=0;i<e;i++)
if(!same(a[i][1],a[i][2])){
merge(a[i][1],a[i][2]);
sum+=a[i][0];
}
cout<<sum<<endl;
}

Output:
EXPERIMENT NO- 5

Aim: Perform the snakes and ladders: The quickest way up.
Source code:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main(){
int t;
cin>>t;
while(t--){
vector<int> a(101);
for(int i=1;i<101;i++)
a[i]=i;
int l,s;
cin>>l;
for(int i=0;i<l;i++)
{
int x,y;
cin>>x>>y;
a[x]=y;
}
cin>>s;
for(int i=0;i<s;i++){
int x,y;
cin>>x>>y;
a[x]=y;
}
vector<int> dist(101,-1);
queue<int> q;
dist[1]=0;
q.push(1);
int ans=-1;
while(!q.empty()&&ans==-1){
int u=q.front();
q.pop();
for(int i=u+1;i<u+7&&i<101;i++)
{
if(dist[a[i]]==-1){
dist[a[i]]=dist[u]+1;
if(a[i]==100){
ans=dist[a[i]];
break;
}
q.push(a[i]);
}
}
}
cout<<ans<<endl;
}
}
Output:
EXPERIMENT NO- 6

Perform Longest Path Algorithm

Source code
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

vector<int> c;
vector<vector<int>> children;
vector<int> dp;

int answer;

void dfs(int v)
{
vector<int> cdp;
for (int u: children[v])
{
dfs(u);
dp[v] = max(dp[v], dp[u]);
cdp.push_back(dp[u]);
}

if (c[v] == 0)
{
dp[v] = 0;
return;
}
dp[v]++;
answer = max(answer, dp[v]);

sort(cdp.rbegin(), cdp.rend());

if (cdp.size() > 1)
answer = max(answer, cdp[0] + cdp[1] + 1);
}

int main()
{
int n;
scanf("%d", &n);
c.resize(n);
children.resize(n);
dp.resize(n);

for (int i = 0; i < n; i++)


scanf("%d", &c[i]);

for (int i = 1; i < n; i++)


{
int p;
scanf("%d", &p);
p--;

children[p].push_back(i);
}

dfs(0);
printf("%d\n", answer);

return 0;
}

You might also like