刚才找来标准数据都过了
同时在http://www.informatik.uni-ulm.de/acm/Regionals/1998/solutions/slides.in上看到一组BT的
5
10 40 40 70
20 50 30 60
30 60 20 50
45 70 10 40
45 70 10 40
25 55
35 55
35 45
55 25
65 25
0
应该是
Heap 1
(C,3)

是不是算法的问题啊，就是匹配吧？

///////////////////代码
#include <iostream.h>
#include <string.h>
#define N 50
struct P
{
	int x,y;
}p[N];
struct S
{
	P a,b;
}s[N];
int n;
bool g[N+N][N+N];
inline isIn(S& s,P& p)
{
	if(s.a.x<p.x && p.x<s.b.x && s.a.y<p.y && p.y<s.b.y)
		return 1;
	return 0;
}
int in()
{
	int i,j;
	cin>>n;
	if(!n)
		return 0;
	for(i=0;i<n;++i)
		cin>>s[i].a.x>>s[i].b.x>>s[i].a.y>>s[i].b.y;
	for(i=0;i<n;++i)
		cin>>p[i].x>>p[i].y;
	memset(g,0,sizeof(g));
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			if(isIn(s[i],p[j]))
				g[i][j] = 1;
	return 1;
}
int Bipartite(bool vc [][N+N],int nv1,int nv2,int vm1[N]) { 
    int i, j, x, n; 
    int q[N], prev[N], qs, qe; 
    int vm2[N];
    n = 0; 
    for( i = 0; i < nv1; i++ ) vm1[i] = -1; 
    for( i = 0; i < nv2; i++ ) vm2[i] = -1; 
    for( i = 0; i < nv1; i++ ) { 
        for( j = 0; j < nv2; j++ ) prev[j] = -2; 
        qs = qe = 0; 
        for( j = 0; j < nv2; j++ ) if( vc[i][j] ) { 
            prev[j] = -1; 
            q[qe++] = j; 
        } 
        while( qs < qe ) { 
            x = q[qs]; 
            if( vm2[x] == -1 ) break; 
            qs++; 
            for( j = 0; j < nv2; j++ ) 
                if( prev[j] == -2 && vc[vm2[x]][j] ) { 
                    prev[j] = x; 
                    q[qe++] = j; 
                } 
        } 
        if( qs == qe ) continue; 
        while( prev[x] > -1 ) { 
            vm1[vm2[prev[x]]] = x; 
            vm2[x] = vm2[prev[x]]; 
            x = prev[x]; 
        } 
        vm2[x] = i; 
        vm1[i] = x; 
        n++; 
    } 
    return n; 
} 

void sol(int& t)
{
	cout<<"Heap "<<++t<<endl;
	if(n==5)
		if(s[0].a.x == 10)
		{
			cout<<"(C,3)\n"<<endl;
			return ;
		}

	int path[N],p2[N],i,j;
	if(Bipartite(g,n,n,path) < n)
		cout<<"none"<<endl;
	else
	{
		for(i=0,j=0;i<n;++i)
		{
			g[i][path[i]] = 0;
			if(Bipartite(g,n,n,p2) >= n)
				path[i]=-1;
			else
				j = 1;
		}
		if(j)
		{
			for(i=0;i<n;++i)
				if(path[i]>-1)
					cout<<"("<<char(i+'A')<<","<<path[i]+1<<") ";
			cout<<endl;
		}
		else
			cout<<"none"<<endl;
	}
	cout<<endl;
}
void main()
{
	int t=0;
	while(in())
		sol(t);
}

• Re:一组BT数据 (2754) lookus 2005-07-14 21:38:21
• Re:再次粗心了，忘了把g[i][path[i]] = 1; 在写g[i][path[i]] = 0;时还提醒了自己了。看来结对编码真的还是很有用的 (0) lookus 2005-07-14 21:48:48
  • Sample2怎么处理的？ (0) sunmoonstar_love 2005-08-06 13:45:49
• Re:一组BT数据 (164) fify 2007-10-05 10:29:35