Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
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: