注册 登录  
 加关注

网易博客网站关停、迁移的公告:

将从2018年11月30日00:00起正式停止网易博客运营
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zxj015

 
 
 

日志

 
 

poj1034 The dog task 最大匹配  

2011-02-12 23:31:35|  分类: 图论 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目讲的是主人出去遛狗。图中有n个景点和m个好玩的地方,主人要沿直线走完n个景点,主人和狗的起点、终点一样,途中狗会离开主人去去一个好玩的地方(每次最多只能一个)并在下一个景点与主人会合,狗的速度是主人的两倍。问最多狗能去几个地方(景点数+能去的最多好玩地方),并且输出狗的行走路线;

构图:把主人走的路段作为X部,景点作为Y部。如果狗在某个路段能到达某个景点就将这两个连线。套用模板求得最大匹配即为狗能到达的最多好玩地方,再加上景点数即可;

Source Code

Problem: 1034 User: 541780774
Memory: 416K Time: 63MS
Language: G++ Result: Accepted

Source Code

#include<stdio.h>  #include<stdlib.h>  #include<string.h>  #include<math.h>  int nx, ny;             // X的點數目、Y的點數目   int mx[101], my[101];   // X各點的配對對象、Y各點的配對對象   bool vy[101];           // 紀錄Graph Traversal拜訪過的點   bool adj[101][101];     // 精簡過的adjacency matrix      // 以DFS建立一棵交錯樹   bool DFS(int x)   {       for (int y=0; y<ny; ++y)           if (adj[x][y] && !vy[y])           {               vy[y] = true;                  // 找到擴充路徑                 if (my[y] == -1 || DFS(my[y]))                {                  mx[x] = y; my[y] = x;                  return true;                  }           }       return false;   }      int bipartite_matching()   {       // 全部的點初始化為未匹配點。       memset(mx, -1, sizeof(mx));          memset(my, -1, sizeof(my));          // 依序把X中的每一個點作為擴充路徑的端點,       // 並嘗試尋找擴充路徑。       int c = 0;       for (int x=0; x<nx; ++x)   //    if (mx[x] == -1)    // x為未匹配點,這行可精簡。           {               // 開始Graph Traversal               memset(vy, false, sizeof(vy));               if (DFS(x)) c++;           }       return c;   }  main()  {           int i,j,n,m,p[101][2],q[101][2],ans;           double a,b,c;           while(scanf("%d%d",&n,&m)!=EOF)           {             memset(adj,0, sizeof(adj));              for(i=0;i<n;i++)                scanf("%d%d",&p[i][0],&p[i][1]);             for(i=0;i<m;i++)                scanf("%d%d",&q[i][0],&q[i][1]);             for(i=0;i<n-1;i++)             for(j=0;j<m;j++)             {               a=sqrt(pow(p[i][0]-p[i+1][0],2)+pow(p[i][1]-p[i+1][1],2));               b=sqrt(pow(q[j][0]-p[i][0],2)+pow(q[j][1]-p[i][1],2));               c=sqrt(pow(q[j][0]-p[i+1][0],2)+pow(q[j][1]-p[i+1][1],2));               if(b+c<=2*a)                 adj[i][j]=1;             }             nx=n-1;             ny=m;             printf("%d\n",n+bipartite_matching());             printf("%d %d ",p[0][0],p[0][1]);             for(i=0;i<n-1;i++)             {               if(my[mx[i]]==i)                printf("%d %d ",q[mx[i]][0],q[mx[i]][1]);               if(i!=n-2)               printf("%d %d ",p[i+1][0],p[i+1][1]);             }             printf("%d %d\n",p[n-1][0],p[n-1][1]);           }                           system("pause");     } 


 

  评论这张
 
阅读(246)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018