Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:理解了。。有图有真相

Posted by yayu_myself at 2010-01-06 21:39:12 on Problem 3041 and last updated at 2010-01-06 21:45:26
In Reply To:还望指点一二。 Posted by:yayu_myself at 2010-01-06 20:59:16
理解了。。以sample为例,把行的点看做left集,列的点看做right集,我们可以画出如下图:
空格用*代替了。。怕没法填充。。

1————————1
*\
**\
2—-\——2
****\/
****/\
***/**\
**/****\
*/******\
3********3 
太佩服我了- -。。

其中每条边都代表一个障碍。。那么目的是要用最少的点消灭障碍,即图中的边,就是

最小覆盖: 最小覆盖要求用最少的点(左右两边的点)让每条边都至少和其中一个点关联。可以证明:最少的点(即覆盖数)=最大匹配数,最大匹配用匈牙利算法,匈牙利不懂见这里:

http://imlazy.ycool.com/post.1603708.html

我的AC如下:

#include <stdio.h>
#include <string.h>
#define N 501
char map[N][N], used[N];
int match[N];

int find(int k, int n)
{
    int i;
    for (i = 1; i <= n; i++)
        if (map[k][i] && !used[i])
        {
            used[i] = 1;
            if (match[i] == -1 || find(match[i], n))
            {
                match[i] = k;
                return 1;
            }
        }
    return 0;
}

int hungary(int n)
{
    int i, res;
    memset(match, -1, sizeof(match));
    res = 0;
    for (i = 1; i <= n; i++)
    {
        memset(used, 0, sizeof(used));
        if (find(i, n)) res++;
    }
    return res;
}

int main(void)
{
    int n, k, i, r, c, res;
    scanf("%d%d", &n, &k);
    for (i = 0; i < k; i++)
    {
        scanf("%d%d", &r, &c);
        map[r][c] = 1;
    }
    printf("%d", hungary(n));
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator