hdu3360National Treasures (最大匹配,拆点法)

National Treasures

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 1038 Accepted Submission(s): 364

Problem Description

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 ) are always a subset of the 12 neighboring cells as shown in the grid below.

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.

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.

Input

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.

Output

For each test case, print the following line:

k. G

Where k is the test case number (starting at one,) and G is the minimum number of additional guards to hire such that all remaining artifacts are secured.

Sample Input

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

Sample Output

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.

Source

2009 ANARC

这题看似与方向有关,当前位置仅仅与它保护的位置是单向的,但并不是是这种,我们来分析一下。

从当前题意可知,保护位置与被保护位置是奇偶对立的,所以我们能够先把点分成奇偶两部分,每一部分内部是不会有关连的,且每一个点是独一无二的,如果是有向的,保护点指向被保护点,建图,左偶右奇,那么如今是要求最小顶点覆盖,先从左指向右求起,求完之后,如果左边没有匹配的点是被保护点,之后再求右指向左的匹配,但右边部分点己经有匹配的点就不用匹配了,那么也就是求右边未匹配的点和左边未匹配的点匹配,这样匹配是一对一的,所以这种匹配也可觉得是求左边未匹配的点与右边未匹配的点相匹配。----------综上得知,这是一个无向区配。

是一个无向的话就有两种求法:

一种是:把图分成奇偶两部分,求最小顶点覆盖。        还有一种是:求最大匹配。

#include<stdio.h>
#include<vector>
#include<iostream>
using namespace std;
int match[2505],vist[2505];
vector<int>map[2505];
int find(int i)
{
    for(int j=0;j<map[i].size();j++)
    if(!vist[map[i][j]])
    {
        vist[map[i][j]]=1;
        if(match[map[i][j]]==-1||find(match[map[i][j]]))
        {
            match[map[i][j]]=i; return 1;
        }
    }
    return 0;
}
int main()
{
    int dir[12][2]={-1,-2,-2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,0,0,1,1,0,0,-1};
    int n,m,mp[55][55],b_w[55][55],bn,wn,k=0;
    while(scanf("%d%d",&n,&m)>0&&n+m!=0)
    {
        for(int i=0;i<n*m;i++)
        {
            map[i].clear(),match[i]=-1;
        }

        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        scanf("%d",&mp[i][j]);
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        if(mp[i][j]!=-1)
        {
            int ti,tj;
            for(int e=0;e<12;e++)
            if(mp[i][j]&(1<<e))
            {
                ti=i+dir[e][0]; tj=j+dir[e][1];
                if(ti>=0&&ti<n&&tj>=0&&tj<m&&mp[ti][tj]!=-1)
                {
                    map[ti*m+tj].push_back(i*m+j);
                    map[i*m+j].push_back(ti*m+tj);
                }
            }
        }
        int ans=0;
        for(int i=0;i<n*m;i++)
        {
            for(int j=0;j<n*m;j++)
            vist[j]=0;
            ans+=find(i);
        }
        printf("%d. %d\n",++k,ans/2);
    }
}
时间: 01-16

hdu3360National Treasures (最大匹配,拆点法)的相关文章

UVa 1658 (拆点法 最小费用流) Admiral

题意: 给出一个有向带权图,求从起点到终点的两条不相交路径使得权值和最小. 分析: 第一次听到“拆点法”这个名词. 把除起点和终点以外的点拆成两个点i和i',然后在这两点之间连一条容量为1,费用为0的边.这样就保证了每个点最多经过一次. 其他有向边的容量也是1 然后求从起点到终点的流量为2(这样就保证了是两条路径)的最小费用流. 本来要在加一个源点和汇点来限制流量的,但是这样弧就多了很多.lrj代码中用了很巧妙的方法,避免了这个问题. 1 #include <bits/stdc++.h> 2

HDU 3998 Sequence (最长递增子序列+最大流SAP,拆点法)经典

Sequence Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1666    Accepted Submission(s): 614 Problem Description There is a sequence X (i.e. x[1], x[2], ..., x[n]). We define increasing subsequ

UVa1658 Admiral(拆点法+最小费用流)

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=51253 [思路] 固定流量的最小费用流. 拆点,将u拆分成u1和u2,连边(u1,u2,1,0)表示只能经过该点一次.跑流量为2的最小费用流. [代码] 1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #include<vector> 5 #define F

1658 - Admiral (拆点+最小费用流)

该题中的拆点法是解决几点容量的通用方法 .  因为只有容量限制的话仍然不能满足每个结点只访问一次这个限制 ,原因很简单,大家画个图就知道了,假设从起点有两条路到同一个结点2,然后又都到末点n,虽然它们满足流量限制但是经过了同一个结点. 那么怎么解决这个问题呢? 答案是:拆点法 . 将一个结点拆成两个结点,由真结点连一条容量为1费用为0的边到假结点,这样之后当我们加边的时候,另起始结点为假结点,终止点为真结点.这样就将这个结点隐性的增加了一个容量属性 . 当然,由于我们要经过起始点和末点两次,所以

本学期最后一周总结及暑假训练计划-司雨寒

一.总结 最近在看大白书的第五章,学了一些更高级的图论算法. 二分图的判定 求无向图的双联通分量(BCC) 以及 割顶 有向图的强连通分量(SCC) 2-SAT 最小瓶颈路,其中O(n2)计算的maxcost数组 可以用二进制优化到O(nlogn) 固定根的最小树形图,朱刘算法 带权二分图最大匹配,没看太懂,对我来说还属于黑盒算法,,还有可行顶标,,匈牙利树,什么鬼 稳定婚姻问题,算法不难理解,感觉该算法的题型较固定 网络流:Dinic算法,ISAP算法(目前还没搞懂).网络流的精髓在于构图,如

第11章例题(紫书)

10/15 这几天先专心刷一下图论的基础题目,也蛮多的,慢慢来... 例题11-1 uva 12219 题意:给你一个表达式,然后又一些子树在之前重复出现过,先要你给这些子树出现的顺序编个号1...N,然后如果重复出现就用编号替代,输出替代之后的表达式. 题解:这是一个表达式树的问题,显示建树,如果让我来写的话,很麻烦,搞不好复杂度是O(n^2),因为字符串是一直扫描下去的,所以就利用一个指针作为全局,然后一直扫下去,就忽略一个左括号,建左树,然后忽略逗号,建右树,忽略右括号,然后一直扫下去,就

HDU 2686 Matrix(最大费用流)

Matrix Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1890    Accepted Submission(s): 1005 Problem Description Yifenfei very like play a number game in the n*n Matrix. A positive integer numbe

HDU 4183 Pahom on Water(最大流)

https://vjudge.net/problem/HDU-4183 题意: 这道题目的英文实在是很难理解啊. 给出n个圆,每个圆有频率,x.y轴和半径r4个属性,每次将频率为400的圆作为起点,频率为789点作为终点.从源点到汇点时必须从频率小的到频率大的,而从汇点到源点时必须从频率大的到频率小的.前提时这两个圆必须严格相交.每个点只能走一次.判断是否能从起点出发到达终点,并再次返回起点. 思路: 其实就是判断最大流是否大于等于2.因为每个点只能走一次,用拆点法. 1 #include<io

uva 1658(最小费用最大流)

题意:一个带权有向图,求起点到终点的两条路径权值之和最小,且两条路径没有公共点(除起点,终点): 分析:拆点法,将u拆成u和u',u-u'容量为1,费用为0,这样就能保证每个点只用一次,起点s-s'容量为2,终点t-t'容量为2保证最大流会求出两条路径,若输入u-v,权为c,则增加边u'-v,容量为1,费用为c. #include <cstdio> #include <iostream> #include <sstream> #include <cmath>

UVa 1660 电视网络(点连通度+最小割最大流+Dinic)

https://vjudge.net/problem/UVA-1660 题意:给出一个无向图,求出点连通度.即最少删除多少个点,使得图不连通. 思路: 如果求线连通度的话,直接求个最大流就可以了.但这题我们删除的是点,用拆点法来使点具有流量的性质,把每个点都拆分为两个点,容量为1,表示可以使用一次.然后,题目中给出的连通的点之间的容量设为INF,因为我们不是要删除这两点之间的线. 最后,我们固定一个源点,枚举汇点,找到最小的删除数. 1 #include<iostream> 2 #includ