首页 > ACM题库 > HDU-杭电 > HDU 3360-National Treasures-二分图-[解题报告]HOJ
2014
03-16

HDU 3360-National Treasures-二分图-[解题报告]HOJ

National Treasures

问题描述 :

The great hall of the national museum has been robbed few times recently. Everyone is now worried about the security of the treasures on display. To help secure the hall, the museum contracted with a private security company to provide additional guards to stay in the great hall and keep an eye on the ancient artifacts. The museum would like to hire the minimum number of additional guards so that the great hall is secured.
The great hall is represented as a two dimensional grid of R × C cells. Some cells are already occupied with the museum’s guards. All remaining cells are occupied by artifacts of different types (statues, sculptures, . . . etc.) which can be replaced by new hired guards. For each artifact, few other cells in the hall are identified as critical points of the artifact depending on the artifact value, type of vault it is kept inside, and few other factors. In other words, if this artifact is going to stay in the hall then all of its critical points must have guards standing on them. A guard standing in a critical position of multiple artifacts can keep an eye on them all. A guard, however,
can not stand in a cell which contains an artifact (instead, you may remove the artifact to allow the guard to stay there). Also you can not remove an artifact and leave the space free (you can only replace an artifact with a new hired guard).
Surveying all the artifacts in the great hall you figured out that the critical points of any artifact (marked by a Kind of a Blur ) are always a subset of the 12 neighboring cells as shown in the grid below.

Kind of a Blur

Accordingly, the type of an artifact can be specified as a non-negative integer where the i-th bit is 1 only if critical point number i from the picture above is a critical point of that artifact. For example an artifact of type 595 (in binary 1001010011) can be pictured as shown in the figure below. Note that bits are numbered from right to left (the right-most bit is bit number 1.) If a critical point of an artifact lies outside the hall grid then it is considered secure.

Kind of a Blur

You are given the layout of the great hall and are asked to find the minimum number of additional guards to hire such that all remaining artifacts are secured.

输入:

Your program will be tested on one or more test cases. Each test case is specified using R+1 lines.
The first line specifies two integers (1<= R,C <= 50) which are the dimensions of the museum hall. The next R lines contain C integers separated by one or more spaces. The j-th integer of the i-th row is -1 if cell (i, j) already contains one of the museum’s guards, otherwise it contains an integer (0 <= T <= 212) representing the type of the artifact in that cell.
The last line of the input file has two zeros.

输出:

Your program will be tested on one or more test cases. Each test case is specified using R+1 lines.
The first line specifies two integers (1<= R,C <= 50) which are the dimensions of the museum hall. The next R lines contain C integers separated by one or more spaces. The j-th integer of the i-th row is -1 if cell (i, j) already contains one of the museum’s guards, otherwise it contains an integer (0 <= T <= 212) representing the type of the artifact in that cell.
The last line of the input file has two zeros.

样例输入:

1 3
512 -1 2048
2 3
512 2560 2048
512 2560 2048
0 0

样例输出:

1. 0
2. 2

Hint
The picture below shows the solution of the second test case where the two artifacts in the middle are replaced by guards. Kind of a Blur

  由于珠宝的临界点必须放置守卫,一个守卫又有可能同时保护许多个珠宝,发现最后要求的便是二分图的最小点集覆盖,这个二分图是这样建的:对于每一个珠宝,如果其临界点没有守卫,那么就在珠宝和该临界点之间连一条边,这条边是必须被覆盖的,所以当整个二分图所有的边都连好后,所要做的就是求最小点集覆盖。

  我看到网上很多人的做法有奇偶染色的,我这里写简单了一点,直接建成无向图,那么最终计算得到的为最小点集覆盖的2倍。

National TreasuresView Code

#include <stdio.h>
 #include <string.h>
 #include <iostream>
 #include <string>
 #include <vector>
 
 using namespace std;
 
 const int maxn = 2500 + 5;
 
 bool vis[maxn];
 int vs[55][55];
 int r, c;
 int link[maxn];
 vector<int> vt[maxn];
 
 int dx[]= {-1, -2, -2, -1, 1, 2,  2,  1, -1, 0, 1,  0};
 int dy[]= {-2, -1,  1,  2, 2, 1, -1, -2,  0, 1, 0, -1};
 
 bool find(int i)
 {
     int size = vt[i].size();
     for(int j = 0; j < size; j ++)
     {
         int k = vt[i][j];
         if(!vis[k])
         {
             vis[k] = true;
             if(link[k] == -1 || find(link[k]))
             {
                 link[k] = i;
                 return true;
             }
         }
     }
     return false;
 }
 
 void init()
 {
     for(int i = 0; i <= r * c; i ++)
         vt[i].clear();
     memset(vs, 0, sizeof vs);
     memset(link, -1, sizeof link);
 }
 
 int main()
 {
     int t = 1;
     while(scanf("%d%d", &r, &c) == 2 && r + c)
     {
         init();
         for(int i = 1; i <= r; i ++)
         {
             for(int j = 1; j <= c; j ++)
             {
                 scanf("%d", &vs[i][j]);
             }
         }
         for(int i = 1; i <= r; i ++)
         for(int j = 1; j <= c; j ++)
             if(vs[i][j] != -1)
             {
                 for(int k = 0; k < 12; k ++)
                 {
                     if((vs[i][j] >> k) & 1)
                     {
                         int x = i + dx[k];
                         int y = j + dy[k];
                         if(x >= 1 && x <= r && y >= 1 && y <= c && vs[x][y] != -1)
                         {
                             vt[c * (i - 1) + j].push_back(c * (x - 1) + y);
                             vt[c * (x - 1) + y].push_back(c * (i - 1) + j);
                         }
                     }
                 }
             }
         int ans = 0;
         for(int i = 1; i <= c * r; i ++)
         {
             memset(vis, false, sizeof vis);
             ans += find(i);
         }
         printf("%d. %d\n", t++, ans / 2);
     }
     return 0;
 }

 

 

参考:http://www.cnblogs.com/huangfeihome/archive/2013/01/19/2868102.html


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  5. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  6. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish