CSTREET

Problem Link

Algorithm:

                    Kruskal

 

View Code

#include <bits/stdc++.h>
using namespace std;

#define INF 10000000
//=======================Starts===========================
typedef unsigned long long ll;
typedef vector vi;
typedef vector< vi > vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef vector vvii;
typedef set si;
typedef map<string, int> msi;

#define all(x) x.begin(), x.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define spresent(c,x) ((c).find(x) != (c).end())  // for set,map
#define present(c,x) (find(all(c),x) != (c).end())  // for vector
#define uu first
#define vv second
#define fr(i,a,b) for(int i=int(a);i<=int(b);++i) #define nfr(i,a,b) for(int i= int(a);i>=int(b);–i)

//=======================Ends===========================
#define mx 10010
struct edge{
ll u,v,w;

};
bool cmp(edge &a,edge &b)
{
return a.w<b.w;

}
ll pr[mx];
void makeset(ll n)
{
for(ll i=0;i<=n;i++)
pr[i]=i;
}
ll find(ll r)
{
if(pr[r]!=r)
return pr[r]=find(pr[r]);
else return r;

}

vector<edge>e;
ll mst(ll n)
{
ll s=0,c=0;
sort(e.begin(),e.end(),cmp);
makeset(n);
for(ll i=0;i<e.size();i++) { ll u=find(e[i].u); ll v=find(e[i].v); if(u!=v) { pr[v]=u; c++; s+=e[i].w; } if(c==n-1) return s; } return -1; } int main() { ll t,p,n,m; cin>>t;
while(t–)
{
cin>>p>>n>>m;

while(m–){
ll u,v,w;
cin>>u>>v>>w;
edge get;
get.u=u;
get.v=v;
get.w=w;
e.pb(get);
}

ll s=mst(n);
cout<<s*p<<endl;
}

}

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s