KM算法模板（邻接表）

二分图最大权匹配，KM算法 写成邻接表形式的

参考：http://hi.baidu.com/lgx_vincent/blog/item/442f99aedd9eb2f1fbed50af.html


#include <stdio.h>
#include <string.h>
#define N 10
#define M N*(N-1)/2
#define inf 0xfffffff
typedef struct node
{
    int key;
    int val; //边权

    struct node *next;
}node;
node *vert[N], edge[M];
int lx[N]; //左边点的顶标
int ly[N]; //右边点的顶标
int usedx[N]; //usedx[i]:左边i点是否在交错路上

int usedy[N]; //usedy[i]:右边i点是否在交错路上
int maty[N]; //maty[i]:与右边i点匹配的左边的点
int slack[N];
int n;
void init()
{
    int m;
    int i, k;
    int x, y, c;
    freopen("KM.in", "r", stdin);
    scanf("%d%d", &n, &m);

    /*建邻接表*/
    for(i=0; i<n; i++)
        vert[i] = NULL;
    k = 0;
    for(i=0; i<m; i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        edge[k].key = y;
        edge[k].val = c;
        edge[k].next = vert[x];
        vert[x] = &edge[k];
        k++;
    }
}
/*寻找*/
int find(int i)
{
    int t;
    node *p;
    usedx[i] = 1; /*要记录左边的点*/
    for(p=vert[i]; p; p=p->next)
    {
        t = lx[i] + ly[p->key] - p->val; /*和匈牙利算法的不同之处, 只有顶标和等于边权才算找到*/
        if(!usedy[p->key] && !t)
        {
            usedy[p->key] = 1;
            if(maty[p->key] == -1 || find(maty[p->key]))
            {
                maty[p->key] = i;
                return 1;
 &nbs

阅读(1817) | 评论(0) | 转发(0) |

0

上一篇：undefined reference to `pow'

下一篇：ural1076 Trash(KM)

给主人留下些什么吧！~~

评论热议

请登录后评论。

登录 注册

关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6