Posted on 2008-08-01 21:21
Hero 阅读(128)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
/* Accepted 2039 C++ 00:00.02 416K */
//还是二部图
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#define llong unsigned long long
#define unint unsigned int
#define printline printf( "\n" )
const int INF = 1000000 ;
const int size = 110 ;
struct NODE {
int x ;
int y ;
};
struct NODE pnode[size] ;
struct NODE dnode[size] ;
int testnum, ct ;
int inp, ind ;
bool link[size][size] ;
int Binmatch( int inn, int inm )
{
int matchnum = 0 ; int dn_node ;
int queue[size*10] ; int head=0, tail = 0 ;//定义队列
int upmatch[size], dnmatch[size] ; int prev[size] ;
memset( upmatch, -1, sizeof(upmatch) ) ;
memset( dnmatch, -1, sizeof(dnmatch) ) ;
for( int i=1; i<=inn; i++ ) {
for( int j=1; j<=inm; j++ ) prev[j] = -2 ;
head = tail = 0 ;
for( int j=1; j<=inm; j++ ) if( link[i][j] )
{ prev[j] = -1 ; queue[tail++] = j ; }
while( head < tail ) {
dn_node = queue[head] ;
if( -1 == dnmatch[dn_node] ) break ;
head++ ;
for( int j=1; j<=inm; j++ ) if( -2==prev[j]&&link[dnmatch[dn_node]][j] )
{ prev[j] = dn_node ; queue[tail++] = j ; }
}
if( head == tail ) continue ;
while( prev[dn_node] > -1 ) {
upmatch[dnmatch[prev[dn_node]]] = dn_node ;
dnmatch[dn_node] = dnmatch[prev[dn_node]] ;
dn_node = prev[dn_node] ;
}
dnmatch[dn_node] = i ; upmatch[i] = dn_node ;
matchnum++ ;
}
printf( "%d\n", matchnum+inp ) ;
for( int i=1; i<inp; i++ ) {
printf( "%d %d ", pnode[i].x, pnode[i].y ) ;
if( upmatch[i] != -1 )
printf( "%d %d ", dnode[upmatch[i]].x, dnode[upmatch[i]].y ) ;
}
printf( "%d %d\n",pnode[inp].x, pnode[inp].y ) ;
return matchnum ;
}
double fdist( int x1, int y1, int x2, int y2 )
{
return sqrt( 1.0*(x1-x2)*(x1-x2) + 1.0*(y1-y2)*(y1-y2) ) ;
}
int main()
{
//freopen( "frac1.in", "r", stdin ) ;
//freopen( "frac1.out","w",stdout ) ;
while( scanf( "%d",&testnum ) != EOF )
//scanf( "%d",&testnum ) ;
{
for( int ct=1; ct<=testnum; ct++ )
{
memset( link, false, sizeof(link) ) ;
scanf( "%d %d",&inp, &ind ) ;
for( int i=1; i<=inp; i++ )
scanf( "%d %d",&pnode[i].x, &pnode[i].y ) ;
for( int i=1; i<=ind; i++ )
scanf( "%d %d",&dnode[i].x, &dnode[i].y ) ;
for( int i=1; i<inp; i++ ) {
double plen = fdist( pnode[i].x, pnode[i].y, pnode[i+1].x, pnode[i+1].y ) ;
for( int j=1; j<=ind; j++ ) {
double dlen = fdist( pnode[i].x, pnode[i].y, dnode[j].x, dnode[j].y ) +
fdist( pnode[i+1].x, pnode[i+1].y, dnode[j].x, dnode[j].y ) ;
if( 2*plen - dlen >= 0 ) link[i][j] = true ;
}
}//构造二部图的link[][]
int matchnum = Binmatch( inp-1, ind ) ;
if( testnum != ct ) printf( "\n" ) ;
}
}//while
return 0 ;
}