Advertisement
LinKin

random

Mar 9th, 2014
152
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.96 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:16777216")
  2.  
  3. #include<stdio.h>
  4. #include<string.h>
  5. #include<math.h>
  6. #include<stdlib.h>
  7. #include<ctype.h>
  8. #include<iostream>
  9. #include<vector>
  10. #include<stack>
  11. #include<queue>
  12. #include<set>
  13. #include<map>
  14. #include<string>
  15. #include<utility>
  16. #include<algorithm>
  17. #include<list>
  18. using namespace std;
  19.  
  20. #define pb push_back
  21. #define IT iterator
  22. #define MP make_pair
  23.  
  24. typedef long long Long;
  25. typedef vector<long> Vl;
  26. typedef pair<long,long> Pll;
  27. typedef map< Pll, long > MPl;
  28.  
  29. vector< Vl > process_graph( Vl &typ )
  30. {
  31.     long i,j,n;
  32.     cin>>n;
  33.     Vl uI( n ),vI( n );
  34.     typ.resize( n );
  35.     for( i=0;i<n;i++ ){
  36.         cin>>uI[i]>>vI[i]>>typ[i];
  37.     }
  38.     vector< Vl > edge( n );
  39.     for( i=0;i<n;i++ ) edge[i].resize( n );
  40.     for( i=0;i<n;i++ ){
  41.         for( j=i+1;j<n;j++ ){
  42.             if( uI[i]==uI[j] || uI[i]==vI[j] ) edge[i][j] = edge[j][i] = true;
  43.             if( vI[i]==uI[j] || vI[i]==vI[j] ) edge[i][j] = edge[j][i] = true;
  44.         }
  45.     }
  46.     return edge;
  47. }
  48.  
  49.  
  50. long maximal_clique( vector< Vl > &edge, Vl cl, Vl nt_set )
  51. {
  52.     long i,j,max_s = cl.size();
  53.     for( i=0;i<edge.size();i++ ){
  54.         if( nt_set[i] ) continue;
  55.         for( j=0;j<cl.size();j++ ){
  56.             if( !edge[i][cl[j]] ) break;
  57.         }
  58.         if( j<cl.size() ) continue;
  59.  
  60.         cl.pb( i );
  61.         max_s = max( max_s, maximal_clique( edge, cl, nt_set ) );
  62.         cl.pop_back();
  63.  
  64.         nt_set[i] = true;
  65.         max_s = max( max_s, maximal_clique( edge, cl, nt_set ) );
  66.         return max_s;
  67.     }
  68.     return max_s;
  69. }
  70.  
  71. int main( void )
  72. {
  73.     long i,j,Icase,k = 0;
  74.  
  75.     freopen("text1.txt","r",stdin );
  76.     //freopen("text7.txt","w",stdout );
  77.  
  78.     Vl typ1,typ2;
  79.     vector< Vl > graph1 = process_graph( typ1 );
  80.     vector< Vl > graph2 = process_graph( typ2 );
  81.  
  82.     MPl assign_index;
  83.     for( i=0;i<graph1.size();i++ ){
  84.         for( j=0;j<graph2.size();j++ ){
  85.             if( typ1[i]==typ2[j] ){
  86.                 assign_index[ MP( i,j ) ] = assign_index.size()-1;
  87.             }
  88.         }
  89.     }
  90.  
  91.     vector< Vl > edge( assign_index.size() );
  92.     for( i=0;i<edge.size();i++ ) edge[i].resize( assign_index.size() );
  93.     for( MPl::IT p1 = assign_index.begin(); p1!=assign_index.end(); p1++ ){
  94.         Pll pu = p1->first;
  95.         for( MPl::IT p2 = p1; p2!=assign_index.end(); p2++ ){
  96.             Pll pv = p2->first;
  97.             if( pu.first==pv.first or pu.second==pv.second ) continue;
  98.             if( graph1[pu.first][pv.first] and graph2[pu.second][pv.second] ){
  99.                 edge[p1->second][p2->second] = edge[p2->second][p1->second] = true;
  100.             }
  101.             else if( !graph1[pu.first][pv.first] and !graph2[pu.second][pv.second] ){
  102.                 edge[p1->second][p2->second] = edge[p2->second][p1->second] = true;
  103.             }
  104.         }
  105.     }
  106.  
  107.     Vl nt_set( assign_index.size() );
  108.     long tot_similarity = maximal_clique( edge, Vl(), nt_set );
  109.     cout<<tot_similarity<<endl;
  110.  
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement