Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:为什么我按解题报告的方法:并查集+搜索,还超时啊?做出来的大牛发个代码看看?

Posted by patch at 2010-08-18 23:56:16 on Problem 1417
In Reply To:为什么我按解题报告的方法:并查集+搜索,还超时啊?做出来的大牛发个代码看看? Posted by:20091000302 at 2010-01-29 21:39:35
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;
const int maxP=1011;
int n, p1, p2, totGroup;
int fa[maxP],rival[maxP],tot[maxP],a[maxP],b[maxP],f[maxP][maxP],w[maxP][maxP],aa[maxP],bb[maxP];
bool v[maxP];
int find( int x )
{
    if ( fa[x]==x ) return x;
    fa[x]=find(fa[x]);
    return fa[x];
}
int unionT( int x, int y )
{
     x=find(x);
     y=find(y);
     if ( x==y || y==0 ) return x;
     if ( x==0 ) return y;
     fa[x]=y;
     tot[y]+=tot[x];
     return y;
}
void getWay( int i, int j )
{
     if ( i==0 ) return;
     if ( w[i][j]==1 )
     {
         getWay( i-1, j-a[i] );
         v[aa[i]]=true;
     }
     else
     {
         getWay( i-1, j-b[i] );
         v[bb[i]]=true;
     }
     return;
}
int main()
{
    while ( cin >> n >> p1 >> p2 )
    {
          if ( n+p1+p2==0 ) break;
          for ( int i=1; i<=p1+p2; i++ )
          {
              fa[i]=i;
              rival[i]=0;
              tot[i]=1;
          }
          for ( int i=1; i<=n; i++ )
          {
              int x,y;
              string s;
              cin >> x >> y >> s;
              if ( s=="yes" )
              {
                   x=find(x);
                   y=find(y);
                   int tx=unionT( x, y ),
                       ty=unionT( rival[x], rival[y] );
                   rival[tx]=ty;
                   rival[ty]=tx;
              }
              else
              {
                  x=find(x);
                  y=find(y);
                  rival[x]=find( rival[x] );
                  rival[y]=find( rival[y] );
                  if ( rival[y]==0 ) rival[y]=x;
                  if ( rival[x]==0 ) rival[x]=y;
                  int tx=unionT( x, rival[y] ),
                      ty=unionT( rival[x], y );
                  rival[tx]=ty;
                  rival[ty]=tx;
              }
          }
          memset( v, false, sizeof(v) );
          totGroup=0;
          for ( int i=1; i<=p1+p2; i++ )
          {
              int x=find( i );
              if ( !v[x] )
              {
                   rival[x]=find( rival[x] );
                   totGroup++;
                   a[totGroup]=tot[x];
                   b[totGroup]=tot[rival[x]];
                   aa[totGroup]=x;
                   bb[totGroup]=rival[x];
                   v[x]=true;
                   v[rival[x]]=true;
              }
          }
          memset( f, 0, sizeof(f) );
          f[0][0]=1;
          for ( int i=1; i<=totGroup; i++ )
          for ( int j=1; j<=p1; j++ )
          {
              if ( j-a[i]>=0 && f[i-1][j-a[i]]>0 )
              {
                   f[i][j]+=f[i-1][j-a[i]];
                   w[i][j]=1;
              }
              if ( j-b[i]>=0 && f[i-1][j-b[i]]>0 )
              {
                   f[i][j]+=f[i-1][j-b[i]];
                   w[i][j]=2;
              }
              if ( f[i][j]>=2 ) f[i][j]=2;
          }

          if ( f[totGroup][p1]==1 || p1==0 )
          {
               memset( v, false, sizeof(v) );
               getWay( totGroup, p1 );
               for ( int i=1; i<=p1+p2; i++ )
               if ( v[ find( i ) ] ) cout << i << endl;
               cout << "end" << endl;
          }
          else cout << "no" << endl;
    }
    return 0;
}


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator