博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hoj 3069 Little Pigs and Wolves 最大匹配
阅读量:5209 次
发布时间:2019-06-14

本文共 1459 字,大约阅读时间需要 4 分钟。

 

/*

 

 

 

题目:

 

       当狼与猪相邻时,狼要吃猪,若狼吃掉一头猪,他不会再吃另一头猪,问狼可以吃掉的猪的最大数目

 

 

 

分析:

 

       狼与猪构成二分图,第i头狼能吃掉第j头猪,则g[i][j] = true即可建图,可以先预处理每一头猪和狼

 

       的序号,然后再建图

 

 

 

*/

 

#include <cstdio>

 

#include <cstring>

 

#define X 105

 

#define M 11

 

char ch[M][M];

 

int ym[X],cal[2][M][M],n,m,nw,np;

 

//int xm[X];

 

bool use[X],g[X][X];

 

bool dfs(int u)

 

{

 

       for(int v=1;v<=np;v++)

 

              if(g[u][v]&&!use[v])

 

              {

 

                     use[v] = true;

 

                     if(ym[v]==-1||dfs(ym[v]))

 

                     {

 

                            //xm[u] = v;

 

                            ym[v] = u;

 

                            return true;

 

                     }

 

              }

 

              return false;

 

}

 

int hungry()

 

{

 

       //memset(xm,-1,sizeof(xm));

 

       memset(ym,-1,sizeof(ym));

 

       int ret = 0;

 

       for(int u=1;u<=nw;u++)

 

              //if(xm[u]==-1)

 

              {

 

                     memset(use,false,sizeof(use));

 

                     if(dfs(u))

 

                            ret++;

 

              }

 

       return ret;

 

}

 

int main()

 

{

 

       freopen("sum.in","r",stdin);

 

       freopen("sum.out","w",stdout);

 

       while(scanf("%d%d",&n,&m)!=EOF)

 

       {

 

              memset(g,false,sizeof(g));

 

              memset(cal,0,sizeof(cal));

 

              for(int i=0;i<n;i++)

 

                     scanf("%s",ch[i]);

 

              nw = np = 0;

 

              for(int i=0;i<n;i++)

 

              {

 

                     for(int j=0;j<m;j++)

 

                            if(ch[i][j]=='W')   //表示这个位置为狼,则给它付号为第++nw

 

                                   cal[1][i][j] = ++nw;

 

                            else if(ch[i][j]=='P')

 

                                   cal[0][i][j] = ++np;

 

              }

 

              for(int i=0;i<n;i++)

 

              {

 

                     for(int j=0;j<m;j++)

 

                            if(ch[i][j]=='W')

 

                                   if(i>0&&ch[i-1][j]=='P')           //上面为猪的话

 

                                          g[cal[1][i][j]][cal[0][i-1][j]] = true;

 

                                   else if(i<n-1&&ch[i+1][j]=='P')      //

 

                                          g[cal[1][i][j]][cal[0][i+1][j]] = true;

 

                                   else if(j>0&&ch[i][j-1]=='P')    //

 

                                          g[cal[1][i][j]][cal[0][i][j-1]] = true;

 

                                   else if(j<m-1&&ch[i][j+1]=='P')     //

 

                                          g[cal[1][i][j]][cal[0][i][j+1]] = true;

 

              }

 

              printf("%d\n",hungry());

 

       }

 

 

 

       return 0;

 

}

 

转载于:https://www.cnblogs.com/yejinru/archive/2012/04/07/2436089.html

你可能感兴趣的文章
Linq使用Join/在Razor中两次反射取属性值
查看>>
[Linux]PHP-FPM与NGINX的两种通讯方式
查看>>
Java实现二分查找
查看>>
优秀员工一定要升职吗
查看>>
[LintCode] 462 Total Occurrence of Target
查看>>
springboot---redis缓存的使用
查看>>
架构图-模型
查看>>
sql常见面试题
查看>>
jQuery总结第一天
查看>>
Java -- Swing 组件使用
查看>>
Software--Architecture--DesignPattern IoC, Factory Method, Source Locator
查看>>
poj1936---subsequence(判断子串)
查看>>
黑马程序员_Java基础枚举类型
查看>>
【redis4 】
查看>>
[ python ] 练习作业 - 2
查看>>
一位90后程序员的自述:如何从年薪3w到30w!
查看>>
HDU-1242-Rescue
查看>>
在.net core上使用Entity FramWork(Db first)
查看>>
Eclipse中如何开启断言(Assert),方法有二
查看>>
System.Net.WebException: 无法显示错误消息,原因是无法找到包含此错误消息的可选资源程序集...
查看>>