Source Code

Problem: 1034  User: yzhw 
Memory: 680K  Time: 172MS 
Language: GCC  Result: Accepted 

Source Code 
# include <stdio.h>
# include <stdbool.h>
# include <math.h>
struct graph
{
   int g;
   struct graph *next;
};
typedef struct
{
   int x1,x2,y1,y2;
   double len;
}point;
point p1[101],p2[101];
struct graph *data[201];
int m,n;
void add(int n1,int n2)
{
     if(data[n1]==NULL)
     {
      data[n1]=(struct graph*)malloc(sizeof(struct graph));
      data[n1]->next=NULL;
      data[n1]->g=n2;
     }
     else
     {
       struct graph *p=data[n1];
       while(p->next!=NULL) p=p->next;
       p->next=(struct graph*)malloc(sizeof(struct graph));
       p=p->next;
       p->next=NULL;
       p->g=n2;
     }
}    
double cul(int x1,int y1,int x2,int y2)
{
       return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}

bool find(int num,bool used[],int map[])
{
     struct graph *p=data[num];
     for(;p!=NULL;p=p->next)
     {
       if(!used[p->g])
       {
         used[p->g]=1;
         if(map[p->g]==0||find(map[p->g],used,map))
         {
           map[p->g]=num;
           return 1;
         }
       }
     }
     return 0;
}
void match(int map[])/*二分图匹配*/ 
{
     bool used[201];
     int i;
     for(i=1;i<=n+m;i++)
     {
       memset(used,0,sizeof(used));
       find(i,used,map);
      
     }
}
int main()
{
    int i,j;
    int map[201];
    scanf("%d %d",&n,&m);
    for(i=1;i<=200;i++) data[i]=NULL;
    for(i=1;i<=n;i++) scanf("%d %d",&p1[i].x1,&p1[i].y1);
    for(i=1;i<=m;i++) scanf("%d %d",&p2[i].x1,&p2[i].y1);
    for(i=1;i<n;i++)
    {
      p1[i].x1+=1000;
      p1[i].y1+=1000;
      p1[i].x2=p1[i+1].x1+1000;
      p1[i].y2=p1[i+1].y1+1000;
    }
    n--;
    for(i=1;i<=m;i++)
    {
      p2[i].x1+=1000;
      p2[i].y1+=1000;
    }
    for(i=1;i<=n;i++) 
       p1[i].len=cul(p1[i].x1,p1[i].y1,p1[i].x2,p1[i].y2);
    /*构建图*/
    for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
      {
         if(cul(p1[i].x1,p1[i].y1,p2[j].x1,p2[j].y1)+cul(p1[i].x2,p1[i].y2,p2[j].x1,p2[j].y1)<=2*p1[i].len+1e-5)
            {
               add(i,j+n);
               add(j+n,i);
            }
      }
    /*---------------------------------------------------*/
    memset(map,0,sizeof(map));
    match(map);/*二分图匹配*/ 
    int rc=n+1;
    for(i=1;i<=n;i++)
      if(map[i]) rc++; 
     printf("%d\n",rc);
     for(i=1;i<=n;i++)
     {
      printf("%d %d ",p1[i].x1-1000,p1[i].y1-1000);
      if(map[i]) printf("%d %d ",p2[map[i]-n].x1-1000,p2[map[i]-n].y1-1000);
     }
     printf("%d %d\n",p1[n].x2-1000,p1[n].y2-1000);
  
     return 0;
}
     

• 水题一个，可惜没有1y，忘了把注释去掉，bs自己！ (0) wangjunyong 2009-09-27 20:29:19
• Re:最大二部图匹配。。172MS AC 附代码 (18) HH_YT 2012-03-12 12:06:58