博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 1068 二分图的最大匹配匈牙利算法
阅读量:7074 次
发布时间:2019-06-28

本文共 1045 字,大约阅读时间需要 3 分钟。

hot3.png

/*
输入格式:
第1行3个整数,V1,V2的节点数目n1,n2,G的边数m
第2-m+1行,每行两个整数t1,t2,代表V1中编号为t1的点和V2中编号为t2的点之间有边相连
输出格式:
1个整数ans,代表最大匹配数
*/
#include <iostream>
using namespace std;
int n1,n2,m,ans;
int n;
int resultt[501]; //记录v2中匹配点的编号 
bool state[501]; //记录v2中每个点是否被搜索过 
bool data[501][501];//记录边的信息 
void init()
{
    int t1,t2;
    memset(data,0,sizeof(data));
    memset(resultt,0,sizeof(resultt));
    ans=0;
    int idd;
    int i;
    int linksum;
    for(i=0;i<n;i++)
    {
        scanf("%d: (%d)",&idd,&linksum);
        int i2;
        int linkn;
        for(i2=0;i2<linksum;i2++)
        {
            scanf("%d",&linkn);
            data[idd][linkn]=true;
        }
    }
    return;
}
bool find(int a)
{
    for(int i=0;i<n;i++)    //这里的i要是未盖点 
    {
        if(data[a][i]==1&&!state[i]) //如果结点i与a相邻并且未被访问过 
        {
            state[i]=true; //标记i为已查找 
            if(resultt[i]==0||find(resultt[i]))    //i未在前一个匹配中或i在前一个匹配中但从i结点出发还有增广路 
            {
                resultt[i]=a;
                return true;
            }
        }
    }
    return false;
}
int main(int argc, char *argv[])
{
    
    while(cin>>n)
    {
        int num=n;
        int i;
        init();
        for(int i=0;i<n;i++)
        {
            memset(state,0,sizeof(state));
            if(find(i))
            {
                ans+=1;
            }
        }
        cout<<num-ans/2<<endl;
        
    }
    return 0;
}

转载于:https://my.oschina.net/hlslml77/blog/204274

你可能感兴趣的文章
redis 的setnx命令
查看>>
在VMware Workstation上安装Kali Linux
查看>>
联想IPMI固件SMASH-CLP 管理
查看>>
glance镜像元数据
查看>>
个人起始
查看>>
二进制单位
查看>>
二叉树的线索化
查看>>
我的友情链接
查看>>
[每日短篇] 10 - Docker 清理无用的镜像
查看>>
我的友情链接
查看>>
thinkphp 生成 excel 文件
查看>>
free()
查看>>
Sort Array By Parity
查看>>
部署 Lync 2010 移动电话(Internal)
查看>>
Android应用程序在新的进程中启动新的Activity的方法和过程分析
查看>>
解析DELL R710服务器迁移操作内容
查看>>
parted用法
查看>>
转 > map和reduce 个数的设定 (Hive优化)经典
查看>>
eclipse安装pydev插件时没有任何错误提示,但是就是装完了后不显示pydev的设置项...
查看>>
IDC:中国安全市场发展潜力巨大
查看>>