糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

HDU 2819 Swap 二分图的最大匹配

这题的目的是,通过一系列交换,让矩阵中A[i, i] (1 <= i <= N)的值全为1。
首先要明确:
如果某行或者某列全是0。那怎么换都没办法的。
否则,一定能换出来。
这个动动脑子想一下可以明白的。

其次要明确:只交换行或者只交换列都是可以换出来的。
这个动动脑子想一下也可以明白的。

明确了这两点,这问题就变成了二分图的匹配问题。
二分图左边的节点为每一行的行号
二分图右边的节点为每一行中出现的“1”对应的列号
这样用匈牙利算法就可以匹配了。

#include <stdio.h>
#include 
<string.h>

#define NR 128

int N;
int mat[NR][NR];
int res[NR];
char vis[NR];

int dfs(int i)
{
    
int j;

    
for (j = 1; j <= N; j++{
        
if (mat[i][j] && !vis[j]) {
            vis[j] 
= 1;
            
if (!res[j] || dfs(res[j])) {
                res[j] 
= i;
                
return 1;
            }

        }

    }


    
return 0;
}


int solve()
{
    
int i, j, k, c, t, m;
    
static int a[NR], b[NR];

    
for (i = 1; i <= N; i++
        
for (j = 1; j <= N; j++
            scanf(
"%d"&mat[i][j]);

    memset(res, 
0sizeof(res));
    
for (i = 1; i <= N; i++{
        memset(vis, 
0sizeof(vis));
        
if (!dfs(i))
            
return 0;
    }


    c 
= 0;
    
for (j = 1; j <= N; j++{
        m 
= j;
        
for (k = j; k <= N; k++)
            
if (res[k] <= res[m])
                m 
= k;
        
if (m != j) {
            a[c] 
= m;
            b[c] 
= j;
            c
++;
            t 
= res[m];
            res[m] 
= res[j];
            res[j] 
= t;
        }

    }


    printf(
"%d\n", c);
    
for (i = 0; i < c; i++)
        printf(
"C %d %d\n", a[i], b[i]);

    
return 1;
}


int main()
{
    
while (scanf("%d"&N) != EOF) 
        
if (!solve())
            printf(
"-1\n");

    
return 0;
}

posted on 2010-10-25 22:01 糯米 阅读(900) 评论(1)  编辑 收藏 引用 所属分类: POJ

评论

# re: HDU 2819 Swap 二分图的最大匹配  回复  更多评论   

博主,你说
如果某行或者某列全是0。那怎么换都没办法的。
否则,一定能换出来。
这个样例你的程序就是 -1
3
1 1 1
0 1 0
0 1 0
2011-11-24 10:59 | tender

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理