/*
3 types of road different for men and women
Let's consider some weird country with N cities and M bidirectional roads of 3 types. It's weird because of some unusual rules about using these roads: men can use roads of types 1 and 3 only and women can use roads of types 2 and 3only. Please answer the following very interesting question: what is maximum number of roads it's possible to destroy that the country will be still connected for both men and women? Connected country is country where it's possible to travel from any city to any other using existing roads.
Input
The first line contains 2 space-separated integer: N and M. Each of the following M lines contain description of one edge: three different space-separated integers: a, b and c. a and b are different and from 1 to N each and denote numbers of vertices that are connected by this edge. c denotes type of this edge.
Output
For each test case output one integer - maximal number of roads it's possible to destroy or -1 if the country is not connected initially for both men and women.
Constraints
1 <= N <= 1000
1 <= M <= 10 000
1 <= a, b <= N
1 <= c <= 3
Sample Input
5 7
1 2 3
2 3 3
3 4 3
5 3 2
5 4 1
5 2 2
1 5 1
ANS-2
****************************EDITORIAL**************]
short explanation
case1-> initiall check graph is conected for men and women or not in the initial phase
case 2->first add node of type 3 for men if not cover all nodes from node of type 1 for men
first add node of type 3 for women if not cover all nodes from node of type 1 for women
detailed explanation
This problem can be solved with greedy approach.
Let's look at this problem in a different way - instead of deleting as much edges as possible, we'll try to pick as few as possible (and remove everything else).
We have graph for men and graph for women. Let's call them M-graph and W-graph. Obviously there is no need to add edge which doesn't connect something in any of graphs. Therefore any edge we take will connect two components in W-graph, or in M-graph, or in both (this is possible only for edges of 3rd type). You need to make 2N-2 merges (N-1 in W-graph and N-1 in M-graph). As we noticed, every edge will do either 1 merge or 2 merges (as we said before, if can make 2 merges only if it is edge of type 3 and it merges two components in both W-graph and M-graph at the same time). This leads us to a simple greedy: let's pick as many edges doing 2 merges as possible.
Add all edges of 3rd type which are merging distinct components. This can be done using DSU. Now you can actually find answer already - if you have used K edges of 3rd type, you made 2K merges already, and you'll need 2N-2-2K more merges, and it will take 1 edge per merge now. If you have a task to print edges, not only their number - it can be done by solving M-graph and W-graph in similar way, but starting with our partially connected by edges of 3rd type graphs instead of empty one.
And don't forget to check that original M-graph and W-graph are connected. Solution without this check will give you only 90 points.
*/
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int myrank[100010];
int parent[100010];
int mark[1010][1010];
int visited[10000000];
typedef long long int lli;
#include<bits/stdc++.h>
list<pair<int,int > > li[100000];
lli read_int(){
char r;bool start=false,neg=false;lli ret=0;
while(true){r=getchar();if((r-'0'<0 || r-'0'>9) && r!='-' && !start){ continue;}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){ break;}if(start)ret*=10;
start=true;if(r=='-')neg=true;else ret+=r-'0';}if(!neg) return ret;else return -ret;}
int par[1000000];
int ra[10000000];
lli dfs(int t1)
{
stack<lli> s;
long long int start= 1;
s.push(start);
visited[start]=1;
lli cov=0;
while(!s.empty())
{
lli start=s.top();
cov++;
s.pop();
list<pair<int,int> > :: iterator it;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(visited[it->first]!=1 && (it->second==t1 || it->second==3))
{
visited[it->first]=1;
s.push(it->first);
}
}
}
return cov;
}
lli find(lli node)
{
if(parent[node]==node)
{
return node;
}
else
find(parent[node]);
}
lli merge(lli a, lli b)
{
lli x=find(a);
lli y=find(b);
if(myrank[x]>myrank[y])
{
parent[y]=x;
}
else
{
parent[x]=y;
if(myrank[x]==myrank[y])
myrank[y]++;
}
}
lli findi(lli node)
{
if(par[node]==node)
{
return node;
}
else
findi(par[node]);
}
lli mergei(lli a, lli b)
{
lli x=findi(a);
lli y=findi(b);
if(ra[x]>ra[y])
{
par[y]=x;
}
else
{
par[x]=y;
if(ra[x]==ra[y])
ra[y]++;
}
}
int main()
{
int t;
lli n,m;
n=read_int();
m=read_int();
vector<pair<pair<lli ,lli >,lli> > vw,vm;
for(lli i=0;i<m;i++)
{
lli a , b,c;
a=read_int();
b=read_int();
c=read_int();
li[a].push_back(make_pair(b,c));
li[b].push_back(make_pair(a,c));
if(c==2)
vw.push_back(make_pair(make_pair(c,a),b) );
if(c==1)
vm.push_back(make_pair(make_pair(c,a),b) );
if(c==3)
{
vm.push_back(make_pair(make_pair(c,a),b) );
vw.push_back(make_pair(make_pair(c,a),b) );
}
}
for(lli i=1;i<=n;i++)
{
parent[i]=i;
par[i]=i;
}
memset(visited,0,sizeof visited);
int cov1=dfs(1);
memset(visited,0,sizeof visited);
int cov2=dfs(2);
if(cov1!=n || cov2!=n)
{
cout<<"-1"<<endl;
return 0;
}
sort(vm.begin(),vm.end());
reverse(vm.begin(),vm.end());
sort(vw.begin(),vw.end());
reverse(vw.begin(),vw.end());
lli cov=0;
long long int cost=1;
for(lli i=0;i<vm.size();i++)
{
lli a,b,c;
a=vm[i].first.second;
b=vm[i].second;
c=vm[i].first.first;
if(find(a)!=find(b))
{
if(mark[a][b]!=1)
{
cov++;
mark[a][b]=1;
}
merge(a,b);
}
}
for(lli i=0;i<vw.size();i++)
{
lli a,b,c;
a=vw[i].first.second;
b=vw[i].second;
c=vw[i].first.first;
if(findi(a)!=findi(b))
{
if(mark[a][b]!=1)
{
cov++;
mark[a][b]=1;
}
mergei(a,b);
}
}
cout<<m-cov<<endl;
return 0;
}
3 types of road different for men and women
Let's consider some weird country with N cities and M bidirectional roads of 3 types. It's weird because of some unusual rules about using these roads: men can use roads of types 1 and 3 only and women can use roads of types 2 and 3only. Please answer the following very interesting question: what is maximum number of roads it's possible to destroy that the country will be still connected for both men and women? Connected country is country where it's possible to travel from any city to any other using existing roads.
Input
The first line contains 2 space-separated integer: N and M. Each of the following M lines contain description of one edge: three different space-separated integers: a, b and c. a and b are different and from 1 to N each and denote numbers of vertices that are connected by this edge. c denotes type of this edge.
Output
For each test case output one integer - maximal number of roads it's possible to destroy or -1 if the country is not connected initially for both men and women.
Constraints
1 <= N <= 1000
1 <= M <= 10 000
1 <= a, b <= N
1 <= c <= 3
Sample Input
5 7
1 2 3
2 3 3
3 4 3
5 3 2
5 4 1
5 2 2
1 5 1
ANS-2
****************************EDITORIAL**************]
short explanation
case1-> initiall check graph is conected for men and women or not in the initial phase
case 2->first add node of type 3 for men if not cover all nodes from node of type 1 for men
first add node of type 3 for women if not cover all nodes from node of type 1 for women
detailed explanation
This problem can be solved with greedy approach.
Let's look at this problem in a different way - instead of deleting as much edges as possible, we'll try to pick as few as possible (and remove everything else).
We have graph for men and graph for women. Let's call them M-graph and W-graph. Obviously there is no need to add edge which doesn't connect something in any of graphs. Therefore any edge we take will connect two components in W-graph, or in M-graph, or in both (this is possible only for edges of 3rd type). You need to make 2N-2 merges (N-1 in W-graph and N-1 in M-graph). As we noticed, every edge will do either 1 merge or 2 merges (as we said before, if can make 2 merges only if it is edge of type 3 and it merges two components in both W-graph and M-graph at the same time). This leads us to a simple greedy: let's pick as many edges doing 2 merges as possible.
Add all edges of 3rd type which are merging distinct components. This can be done using DSU. Now you can actually find answer already - if you have used K edges of 3rd type, you made 2K merges already, and you'll need 2N-2-2K more merges, and it will take 1 edge per merge now. If you have a task to print edges, not only their number - it can be done by solving M-graph and W-graph in similar way, but starting with our partially connected by edges of 3rd type graphs instead of empty one.
And don't forget to check that original M-graph and W-graph are connected. Solution without this check will give you only 90 points.
*/
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int myrank[100010];
int parent[100010];
int mark[1010][1010];
int visited[10000000];
typedef long long int lli;
#include<bits/stdc++.h>
list<pair<int,int > > li[100000];
lli read_int(){
char r;bool start=false,neg=false;lli ret=0;
while(true){r=getchar();if((r-'0'<0 || r-'0'>9) && r!='-' && !start){ continue;}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){ break;}if(start)ret*=10;
start=true;if(r=='-')neg=true;else ret+=r-'0';}if(!neg) return ret;else return -ret;}
int par[1000000];
int ra[10000000];
lli dfs(int t1)
{
stack<lli> s;
long long int start= 1;
s.push(start);
visited[start]=1;
lli cov=0;
while(!s.empty())
{
lli start=s.top();
cov++;
s.pop();
list<pair<int,int> > :: iterator it;
for(it=li[start].begin();it!=li[start].end();it++)
{
if(visited[it->first]!=1 && (it->second==t1 || it->second==3))
{
visited[it->first]=1;
s.push(it->first);
}
}
}
return cov;
}
lli find(lli node)
{
if(parent[node]==node)
{
return node;
}
else
find(parent[node]);
}
lli merge(lli a, lli b)
{
lli x=find(a);
lli y=find(b);
if(myrank[x]>myrank[y])
{
parent[y]=x;
}
else
{
parent[x]=y;
if(myrank[x]==myrank[y])
myrank[y]++;
}
}
lli findi(lli node)
{
if(par[node]==node)
{
return node;
}
else
findi(par[node]);
}
lli mergei(lli a, lli b)
{
lli x=findi(a);
lli y=findi(b);
if(ra[x]>ra[y])
{
par[y]=x;
}
else
{
par[x]=y;
if(ra[x]==ra[y])
ra[y]++;
}
}
int main()
{
int t;
lli n,m;
n=read_int();
m=read_int();
vector<pair<pair<lli ,lli >,lli> > vw,vm;
for(lli i=0;i<m;i++)
{
lli a , b,c;
a=read_int();
b=read_int();
c=read_int();
li[a].push_back(make_pair(b,c));
li[b].push_back(make_pair(a,c));
if(c==2)
vw.push_back(make_pair(make_pair(c,a),b) );
if(c==1)
vm.push_back(make_pair(make_pair(c,a),b) );
if(c==3)
{
vm.push_back(make_pair(make_pair(c,a),b) );
vw.push_back(make_pair(make_pair(c,a),b) );
}
}
for(lli i=1;i<=n;i++)
{
parent[i]=i;
par[i]=i;
}
memset(visited,0,sizeof visited);
int cov1=dfs(1);
memset(visited,0,sizeof visited);
int cov2=dfs(2);
if(cov1!=n || cov2!=n)
{
cout<<"-1"<<endl;
return 0;
}
sort(vm.begin(),vm.end());
reverse(vm.begin(),vm.end());
sort(vw.begin(),vw.end());
reverse(vw.begin(),vw.end());
lli cov=0;
long long int cost=1;
for(lli i=0;i<vm.size();i++)
{
lli a,b,c;
a=vm[i].first.second;
b=vm[i].second;
c=vm[i].first.first;
if(find(a)!=find(b))
{
if(mark[a][b]!=1)
{
cov++;
mark[a][b]=1;
}
merge(a,b);
}
}
for(lli i=0;i<vw.size();i++)
{
lli a,b,c;
a=vw[i].first.second;
b=vw[i].second;
c=vw[i].first.first;
if(findi(a)!=findi(b))
{
if(mark[a][b]!=1)
{
cov++;
mark[a][b]=1;
}
mergei(a,b);
}
}
cout<<m-cov<<endl;
return 0;
}
No comments:
Post a Comment