Coal Scam
Chef has entered the politics of Byteland. He is a minister in the coal department of the government. Recently, he has been assigned a project on constructing special bidirectional roads for transferring coals in such a way that the whole country is connected by a road network.
Different companies submitted their proposal of roads that they could build along with their estimated cost of the road. Chef has to select a subset of these proposed roads so that all cities of the country are connected.
Chef, corrupt as he is, managed to submit bids by his own company for certain roads. If some of his proposed roads are selected, he'd use low grade material. We can safely assume that the cost of building these roads is nothing to him. He would still receive the price he has quoted in the bid and hence, would make as much profit. He wants to choose some subset of proposed roads so that his own profit is maximised.
Byteland consists of N cities. There are M1 proposals to build roads by companies other than Chef's. Chef's company has proposed to build M2 roads. Chef wants to choose a subset of these roads in such a way that for each pair of cities, there is exactly one path of roads connecting them. The profit Chef will gain is equal to the sum of costs of the roads chosen from among those made by Chef's company.
Help Chef choose the roads in such a way that his profit is maximized. If there are multiple ways to achieve that, choose the way where the sum of costs of all chosen roads is minimized.
Input
The first line of the input contains a number T, the number of test cases. This is followed by the input for each test case one by one. The first line of each test case contains three space-separated integers N, M1, and M2. Then M1 lines follow, each containing a description of a road proposed by other companies. Each of these lines contains three space-separated integers u, v, and c, where u and v denote the end points of the road and c denotes the associated cost. Then M2 lines follow, each containing a description of a road proposed by Chef's company in the same format.
Output
Output a single line for each test case. If it is impossible to choose a subset of the roads in such a way that for each pair of cities, there is exactly one path of roads connecting them, output a single line containing "Impossible" (quotes for clarity and starts with an uppercase 'I') for that test case. Otherwise, output a single line containing two space-separated integers: the maximum profit Chef can gain and the minimum total cost of the chosen roads that yields the maximum profit.
Example
Input: 2 3 2 1 0 1 5 1 2 4 0 1 10 3 1 1 0 1 1 0 1 3 Output: 10 14 Impossible
Constraints
1 ≤ T ≤ 5
2 ≤ N ≤ 5,000
1 ≤ M1 ≤ 20,000
1 ≤ M2 ≤ 20,000
For each proposed road, the end points will be two different cities.
There may be several proposed roads between the same pair of cities.
For each proposed road, 0 ≤ c ≤ 1,000,000,000
2 ≤ N ≤ 5,000
1 ≤ M1 ≤ 20,000
1 ≤ M2 ≤ 20,000
For each proposed road, the end points will be two different cities.
There may be several proposed roads between the same pair of cities.
For each proposed road, 0 ≤ c ≤ 1,000,000,000
Each input file will not be larger than 4 MB (4,000,000,000 bytes) in size.
---------------------------------------EDITORIAL---------------
THIS IS A SIMPLE MST PROBLEM ONLY DIFFERENCE IS THAT SOME OF THE EDGE IS FIXED .. AND WE NEED TO USE UNION FIND TO DECIDE REST REMAINING EDGES OF MST..
first connect all nodes which are given by minister .. also first sort all input in decreasing order of cost of minister since minister want to make more money so it will construct more cost node ..now try to connect nodes 1 by 1 using union find also maintain a graph of selected node and edge so that latter we can check that is there any disconnected graph .. after that
now take input of other builders and sort them and in this case try to connect low cost edge(incresing order of cost ) first soo use in incresing sorted order also maintain graph if any new node added (if found by union find that it can be connect )..
finally ans will be
apply bfs on constructed graph if visit all nodes than
benifit of minister = cost in first part , and total cost = ans of first +second part
else answer=IMPOSSIBLE
==========================CODE======================================
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int lli;
lli rank[1000100];
lli par[1000100];
#include<bits/stdc++.h>
lli find(lli a)
{
if(par[a]!=par[par[a]])
{
par[a]=find(par[a]);
}
return par[a];
}
lli merge(lli a, lli b)
{
lli x=find(a);
lli y=find(b);
if(rank[x]>rank[y])
{
par[y]=x;
}
else
{
par[x]=y;
if(rank[x]==rank[y])
rank[y]++;
}
}
int main()
{
int t;
cin>>t;
while(t--)
{
lli n,m1,m2;
list<lli> li[10000+100];
cin>>n>>m1>>m2;
int visited[100000];
for(lli i=0;i<=n+10000;i++)
{
par[i]=i;
visited[i]=0;
rank[i]=0;
}
lli c , a,b;
vector<pair<pair<lli,lli>, lli > > v;
for(lli i=0;i<m1;i++)
{
cin>>a>>b>>c;
v.push_back(make_pair(make_pair(c,a),b));
}
sort(v.begin(),v .end());
lli cc= 0,pub=0;
//cout<<"reading chef "<<endl;
vector<pair<pair<lli,lli>, lli > > v2;
for(lli i=0;i<m2;i++)
{
cin>>a>>b>>c;
v2.push_back(make_pair(make_pair(c,a),b));
}
sort(v2.begin(),v2.end());
reverse(v2.begin(),v2.end());
for(lli i=0;i<m2;i++)
{
a=v2[i].first.second;
b=v2[i].second;
c=v2[i].first.first;
if(find(a)!=find(b))
{
cc+=c;
merge(a,b);
li[a].push_back(b);
li[b].push_back(a);
}
}
for(int i=0;i<m1;i++)
{
a=v[i].first.second;
b=v[i].second;
c=v[i].first.first;
if(find(a)!=find(b))
{
pub+=c;
merge(a,b);
li[a].push_back(b);
li[b].push_back(a);
}
}
lli count=0;
stack<lli>s;
s.push(0);
visited[0]=1;
while(!s.empty())
{
lli start=s.top();
s.pop();
count++;
list<lli> :: iterator it;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(!visited[*it])
{
visited[*it]=1;
s.push(*it);
}
}
}
// cout<<" count is "<<count<<endl;
if(count==n)
cout<<cc<<" "<<cc+pub<<endl;
else
cout<<"Impossible"<<endl;
// for(int i=0;i<n;i++) cout<<par[i]<<" "<<i<<endl;*/
}
return 0;
}
No comments:
Post a Comment