Chinaunix首页 | 论坛 | 博客
  • 博客访问: 474158
  • 博文数量: 117
  • 博客积分: 3195
  • 博客等级: 中校
  • 技术积分: 1156
  • 用 户 组: 普通用户
  • 注册时间: 2009-08-04 01:44
文章分类

全部博文(117)

文章存档

2012年(5)

2011年(5)

2010年(46)

2009年(61)

我的朋友

分类: C/C++

2010-05-14 12:21:10

二分图最大权匹配,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

阅读(1834) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~