Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:16777216")
- #include<stdio.h>
- #include<string.h>
- #include<math.h>
- #include<stdlib.h>
- #include<ctype.h>
- #include<iostream>
- #include<vector>
- #include<stack>
- #include<queue>
- #include<set>
- #include<map>
- #include<string>
- #include<utility>
- #include<algorithm>
- #include<list>
- using namespace std;
- #define pb push_back
- #define IT iterator
- #define MP make_pair
- typedef long long Long;
- typedef vector<long> Vl;
- typedef pair<long,long> Pll;
- typedef map< Pll, long > MPl;
- vector< Vl > process_graph( Vl &typ )
- {
- long i,j,n;
- cin>>n;
- Vl uI( n ),vI( n );
- typ.resize( n );
- for( i=0;i<n;i++ ){
- cin>>uI[i]>>vI[i]>>typ[i];
- }
- vector< Vl > edge( n );
- for( i=0;i<n;i++ ) edge[i].resize( n );
- for( i=0;i<n;i++ ){
- for( j=i+1;j<n;j++ ){
- if( uI[i]==uI[j] || uI[i]==vI[j] ) edge[i][j] = edge[j][i] = true;
- if( vI[i]==uI[j] || vI[i]==vI[j] ) edge[i][j] = edge[j][i] = true;
- }
- }
- return edge;
- }
- long maximal_clique( vector< Vl > &edge, Vl cl, Vl nt_set )
- {
- long i,j,max_s = cl.size();
- for( i=0;i<edge.size();i++ ){
- if( nt_set[i] ) continue;
- for( j=0;j<cl.size();j++ ){
- if( !edge[i][cl[j]] ) break;
- }
- if( j<cl.size() ) continue;
- cl.pb( i );
- max_s = max( max_s, maximal_clique( edge, cl, nt_set ) );
- cl.pop_back();
- nt_set[i] = true;
- max_s = max( max_s, maximal_clique( edge, cl, nt_set ) );
- return max_s;
- }
- return max_s;
- }
- int main( void )
- {
- long i,j,Icase,k = 0;
- freopen("text1.txt","r",stdin );
- //freopen("text7.txt","w",stdout );
- Vl typ1,typ2;
- vector< Vl > graph1 = process_graph( typ1 );
- vector< Vl > graph2 = process_graph( typ2 );
- MPl assign_index;
- for( i=0;i<graph1.size();i++ ){
- for( j=0;j<graph2.size();j++ ){
- if( typ1[i]==typ2[j] ){
- assign_index[ MP( i,j ) ] = assign_index.size()-1;
- }
- }
- }
- vector< Vl > edge( assign_index.size() );
- for( i=0;i<edge.size();i++ ) edge[i].resize( assign_index.size() );
- for( MPl::IT p1 = assign_index.begin(); p1!=assign_index.end(); p1++ ){
- Pll pu = p1->first;
- for( MPl::IT p2 = p1; p2!=assign_index.end(); p2++ ){
- Pll pv = p2->first;
- if( pu.first==pv.first or pu.second==pv.second ) continue;
- if( graph1[pu.first][pv.first] and graph2[pu.second][pv.second] ){
- edge[p1->second][p2->second] = edge[p2->second][p1->second] = true;
- }
- else if( !graph1[pu.first][pv.first] and !graph2[pu.second][pv.second] ){
- edge[p1->second][p2->second] = edge[p2->second][p1->second] = true;
- }
- }
- }
- Vl nt_set( assign_index.size() );
- long tot_similarity = maximal_clique( edge, Vl(), nt_set );
- cout<<tot_similarity<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement