设为首页 加入收藏

TOP

poj 2594 Treasure Exploration 最小路径覆盖/最大匹配
2015-07-22 20:10:00 来源: 作者: 【 】 浏览:9
Tags:poj 2594 Treasure Exploration 最小 路径 覆盖 最大 匹配

?

?

#include
  
   
#include
   
     const int N=510; int line[N][N]; int mac[N]; int used[N]; int n,m; void floyd() { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { for(int k=1;k<=n;k++) { if(line[j][i] && line[i][k]) { line[j][k]=1; } } } } } bool get_path(int u) { for(int i=1;i<=n;i++) { if(line[u][i] && !used[i]) { used[i]=1; if(mac[i]==-1 || get_path(mac[i])) { mac[i]=u; return 1; } } } return 0; } int MaxMatch() { int num=0; memset(mac,-1,sizeof(mac)); for(int i=1;i<=n;i++) { memset(used,0,sizeof(used)); if(get_path(i)) num++; } return num; } int main() { while(~scanf(%d%d,&n,&m),m||n) { memset(line,0,sizeof(line)); for(int i=0;i
    
     

?

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇hdu5288OO’s Sequence 下一篇hdu5288(2015多校1)OO’s Sequence

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: