带权最大匹配

HDU 2853 Assignment

Posted on

最近在水KM算法 只要把KM理解了 至今写到的大部分都是水题

唯独这题让我写了很长时间 看了其他人的博客才明白什么叫建图的巧妙和重要性

题意 有n家公司和m个任务 所有任务和公司都已经匹配好了 要求在尽量保留原有匹配的基础上 求得最优匹配 输出改变的数量 和 改变后增加的权值

巧妙的思路来了 首先对于所有输入的权值增大K倍 这里的K必须大于n 再对原匹配的权值都加 1 这样 原匹配的优先级将大于其他匹配

再套模板 这时出来的结果 将是匹配权值数的K倍再加上原匹配的数目 (所以这里就体现了K大于n的原因了 若是K小于n 那么大于K的部分将可能成为原匹配数目,结果将乱套………………

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;
const int maxn=55;
const int inf=0x3f3f3f3f;
int cnum,mnum;
int linky[maxn],lx[maxn],ly[maxn];
bool visx[maxn],visy[maxn];
int g[maxn][maxn],slack[maxn];

bool dfs(int x)
{
    visx[x]=true;
    for(int y=1;y<=mnum;y++)
    {
        if(visy[y]) continue;
        int t=lx[x]+ly[y]-g[x][y];
        if(t==0)
        {
            visy[y]=true;
            if(linky[y]==-1||dfs(linky[y]))
            {
                linky[y]=x;
                return true;
            }
        }
        else if(slack[y]>t) slack[y]=t;
    }
    return false;
}

int KM()
{
    memset(linky,-1,sizeof linky);
    memset(ly,0,sizeof ly);
    for(int i=1;i<=cnum;i++)
    {
        lx[i]=-inf;
        for(int j=1;j<=mnum;j++)
            if(g[i][j]>lx[i]) lx[i]=g[i][j];
    }
    for(int x=1;x<=cnum;x++)
    {
        for(int i=1;i<=mnum;i++) slack[i]=inf; 
        while(true)
        {
            memset(visx,false,sizeof visx);
            memset(visy,false,sizeof visy);
            if(dfs(x)) break;
            int d=inf;
            for(int i=1;i<=mnum;i++)
                if(!visy[i]&&d>slack[i]) d=slack[i];
            for(int i=1;i<=cnum;i++)
                if(visx[i]) lx[i]-=d;
            for(int i=1;i<=mnum;i++)
                if(visy[i]) ly[i]+=d;
                else slack[i]-=d;
        }
    }
    int result=0;
    for(int i=1;i<=mnum;i++)
    {
        if(linky[i]>-1)
            result+=g[linky[i]][i];
    }
    return result;
}

int main()
{
    int eff;
    while(scanf("%d%d",&cnum,&mnum)!=EOF)
    {
        int prenum=0,m;
        for(int i=1;i<=cnum;i++)
            for(int j=1;j<=mnum;j++)
            {
                scanf("%d",&eff);
                g[i][j]=eff*100;
            }
        for(int i=1;i<=cnum;i++)
        {
            scanf("%d",&m);
            prenum+=g[i][m];
            g[i][m]++;
        }
        int ans=KM();
        printf("%d %d\n",cnum-ans%100,ans/100-prenum/100);

    }
    return 0;
}
带权最大匹配

KM 算法学习

Posted on

KM算法 用于求二分图的最佳完美匹配 即权值最大的完美匹配

如果你也是个刚来学习KM算法的人 大概的用途肯定还是知道的吧 还是直接说重点吧

首先 理解KM算法前 必须有以下3个概念

1.可行顶标 对于一个赋值二分图G(x,y,e,w) (x,y 代表二分图的两边顶点标号 e代表边 w代表边的权值 ) 我们对两边的每一个顶点都赋予一个额外的值 使得对于二分图G内的所有边 e=xy 均有 lx(x)+ly(y)>=w(xy)

其实不管什么样的图 什么样的边权 可行顶标必然存在 例如 lx(x)=max w(xy) ly(y)=0

2.在已经赋值可行顶标的二分图中 保留所有lx(x)+ly(y)=w(x)(y) 的边 删去其他的边 形成的新的图称为生成子图

3.在生成子图中的任意一个完美匹配都是最佳完美匹配 反过来 G的任意一个最佳完美匹配都包含在 生成子图中

可能第三条定理来的有些突然 有点让人懵逼 但是你只要稍微想一下 你就会发现这很明显

因为这个匹配 他所有权值之和就是可行顶标之和 而 可行顶标之和必然是权值之和最大的(因为第一条

但问题是 对于当前顶标所推出的生成子图 并不一定存在完美匹配 这时,可以用某种方法对顶标进行调整。调整的方法是:根据最后一次不成功的寻找交错路的DFS,取所有i被访问到而j没被访问到的边(i,j)的lx[i]+ly[j]-w[i][j]的最小值d。将交错树中的所有左端点的顶标减小d,右端点的顶标增加d。经过这样的调整以后:原本在导出子图里面的边,两边的顶标都变了,不等式的等号仍然成立,仍然在导出子图里面;原本不在导出子图里面的边,它的左端点的顶标减小了,右端点的顶标没有变,而且由于d的定义,不等式仍然成立,所以他就可能进入了导出子图里。

如果还看不懂 我只能贴上我学习过程看的博客了 毕竟只有文字可能不好理解 我又懒

上面的文字理解来源

萌萌哒的妹子写的图文详解

最后是来几套题

最大匹配

HDU 1350 Taxi Cab Scheme

Posted on

题意: 老司机接客的故事 有很多顾客想要去一些地方 给你起点和终点 问最少需要多少老司机 (起点不计时

主要是坐标建图还是第一次写到 就写个题解压压惊 其实还是按照题意来就好了 再用数组链表实现邻接表存图 好像写烦了 慢了点

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;
const int maxn=505;
int n,cnt;
int head[maxn],link[maxn];
bool vis[maxn];
struct point
{
    int x,y;
};
inline int dist(const point& a,const point& b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}
struct edge
{
    point st,en;
    int st_time,en_time;
    void cal()
    {
        en_time=st_time+dist(st,en);
    }
} road[maxn];
struct path
{
    int st,en;
    int nxt;
}e[maxn*maxn];

void add(int u,int v)
{
    e[cnt].st=u;
    e[cnt].en=v;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}

void creat_gragh()
{
    memset(head,-1,sizeof head);
    cnt=0;
    for(int i=1; i<n; i++)
        for(int j=i+1; j<=n; j++)
            if(road[i].en_time+dist(road[i].en,road[j].st)<road[j].st_time) add(i,j);
}

bool dfs(int x)
{
    for(int i=head[x];i!=-1;i=e[i].nxt)
    {
        int t=e[i].en;
        if(!vis[t])
        {
            vis[t]=true;
            if(link[t]==-1||dfs(link[t]))
            {
                link[t]=x;
                return true;
            }
        }
    }
    return false;
}

int hungary()
{
    int num=0;
    memset(link,-1,sizeof link);
    for(int i=1;i<=n;i++)
    {
        memset(vis,false,sizeof vis);
        if(dfs(i)) num++;
    }
    return num;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int test,hh,mm;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d",&n);
        for(int i=1; i<=n; i++)
        {
            scanf("%d:%d %d %d %d %d",&hh,&mm,&road[i].st.x,&road[i].st.y,&road[i].en.x,&road[i].en.y);
            road[i].st_time=hh*60+mm;
            road[i].cal();
        }
        creat_gragh();
        printf("%d\n",n-hungary());
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
最大匹配

HDU 1498 50 years, 50 colors

Posted on

尽管是大水题 但是再怎么说就是自己走过的路啊
不过现在只是二分图入门阶段 到现在为止接触的一些题目真的是太水了 只要 吧题目理解 套个模板就好了 所以这里就只拿一个hdu1498作为水题典例

简单说 题目是个最小点覆盖问题 二分图的最小点覆盖==最大匹配数 问的是哪些数字在k步操作内无法完全覆盖 也就是说最大匹配大于k的有哪些

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <set>
#include <iterator>

using namespace std;
const int maxn=105;
int n,k;
int g[maxn][maxn],link[maxn];
bool vis[maxn];
set<int> kao;
int hungary(int);
bool dfs(int,int);

int main()
{
    int temp,ans[maxn];
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        if(n==0&&k==0) break;
        kao.clear();
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                scanf("%d",&temp);
                kao.insert(temp);
                g[i][j]=temp;
            }
        int num=0,kase=0;
        for(set<int>::iterator it=kao.begin(); it!=kao.end(); it++)
        {
            temp=hungary(*it);
            if(temp>k) ans[num++]=*it;
        }
        if(num==0) printf("-1");
        else
        {
            sort(ans,ans+num);
            for(int i=0; i<num; i++)
            {
                if(kase++) putchar(' ');
                printf("%d",ans[i]);
            }
        }
        puts("");
    }
    return 0;
}
int hungary(int key)
{
    int num=0;
    for(int i=1; i<=n; i++) link[i]=-1;
    memset(link,-1,sizeof link);
    for(int i=1; i<=n; i++)
    {
        memset(vis,false,sizeof vis);
        if(dfs(i,key)) num++;
    }
    return num;
}

bool dfs(int x,int key)
{
    for(int i=1; i<=n; i++)
        if(!vis[i]&&g[x][i]==key)
        {
            vis[i]=true;
            if(link[i]==-1||dfs(link[i],key))
            {
                link[i]=x;
                return true;
            }
        }
    return false;
}
最大匹配

FZU 2039 Pets

Posted on

匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

其实说白了 这个算法用途有限 只能求二分图的最大匹配(如果没有任何扩展,毕竟我是鶸……

题目是一个人与狗的故事
这里每个人都想日狗 所以肯定是一对一的啊 但总共有 n个人 m只狗 e个先决条件
这些条件中 第ai个人不喜欢第bi只狗
问最多能让多少人 日到狗

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1100;
int n,m,qnum;
int cus[maxn];
bool vis[maxn],g[maxn][maxn];

void init()
{
    memset(g,true,sizeof g);
    memset(cus,0,sizeof cus);
    int u,v;
    for(int i=0; i<qnum; i++)
    {
        scanf("%d%d",&u,&v);
        g[u][v]=false;
    }
}

bool fin(int a)
{
    for(int i=1; i<=m; i++)
        if(g[a][i]&&!vis[i])
        {
            vis[i]=true;
            if(cus[i]==0||fin(cus[i]))
            {
                cus[i]=a;
                return true;
            }
        }
    return false;
}

int main()
{
    int test;
    scanf("%d",&test);
    for(int t=1; t<=test; t++)
    {
        scanf("%d%d%d",&n,&m,&qnum);
        init();
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            memset(vis,false,sizeof vis);
            if(fin(i)) ans++;
        }
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}