二分图染色

洛谷 1155 双栈排序

Posted on

别多说了,神题。

写不来,看得是大佬的题解
很妙,没想到用二分图染色,但是二分图染色的模型的确很适合这个题目。

不过关键还是那个判定定理。

题意:
给你一个序列,要你用两个栈给它排序,问你这个序列是否能排序成功。

思路:
上面的链接很详细,我这里简单说一蛤。
首先必须注意到判定两个数必须在两个不同的栈的充要条件。

S[i],S[j]两个元素不能进入同一个栈 <=> 存在k,满足i<j<k,使得S[k]<S[i]<S[j]. 证明略过,请参考sqybi.尝试后可以发现结论P是正确的.

我们首先用\( O( n^2 ) \) 的复杂度预处理出必须在两个栈的位置,并对其连边,再对其染色,对没有限制的优先放在第一个栈中因为要字典序最小

通过染色判定,不能形成二分图则输出0,否则模拟输出序列。

#include <bits/stdc++.h>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;

int ary[maxn];
int bmin[maxn];
int color[maxn];
int st1[maxn], st2[maxn], t1, t2;

vector<int> G[maxn];

bool dfs(int u, int c)
{
    color[u] = c;
    int sz = G[u].size(), v;
    for (int i = 0; i < sz; i++) {
        v = G[u][i];
        if (!color[v] && !dfs(v, 3 - c))
            return false;
        else if (color[v] == c)
            return false;
    }
    return true;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", ary + i);
    bmin[n] = inf;
    for (int i = n - 1; i >= 0; i--)
        bmin[i] = min(bmin[i + 1], ary[i]);
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (ary[i] < ary[j] && bmin[j + 1] < ary[i])
                G[i].push_back(j), G[j].push_back(i);
    for (int i = 0; i < n; i++)
        if (!color[i] && !dfs(i, 1)) {
            puts("0");
            return 0;
        }
    int cur = 1;
    for (int i = 0; i < n; i++) {
        if (color[i] == 1) {
            printf("a ");
            st1[++t1] = ary[i];
        } else {
            printf("c ");
            st2[++t2] = ary[i];
        }
        while (st1[t1] == cur || st2[t2] == cur) {
            if (st1[t1] == cur)
                printf("b "), t1--;
            else
                printf("d "), t2--;
            cur++;
        }
    }
    return 0;
}
多重匹配

HDU 3605 Escape

Posted on

多重匹配模板题……也是从薛昊那偷来的题……

貌似有更好的做法……看到了什么二进制压缩什么的……

这题数据很大,时间卡的很紧,使得我对模板使用了解更深了一点。

题意:
地球上有n个人要移民,有m的星球可以提供移民,这些人都很挑剔,只去自己感兴趣的星球,问是否存在一个方案使得每个人都能去自己感兴趣的星球。
每个星球容纳人数有限。
人数1e5,星球数 10。

思路:
二分图多重匹配裸题。这里如果你对模板使用比较了解肯定是一发水过的……

这里要对数组强调一下。 记 左元数组 l ,右元数组 r

  • mat[n][m] 二维可达矩阵。
  • link[m][n] 二维连接矩阵,记录每个 r 元素 连接的 l 元素
  • vis[m] 单次dfs的访问记录数组
  • vlink[m] 记录每个 r 元素连接的 l 元素数量
  • num[m] 记录每个 r 元素的限制数量

简单说,只有可达矩阵是n开头的!!!!!!

靠着输入挂800+ms……

AC Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;
const int maxn = 1e5 + 5;
const int maxm = 12;
const int inf = 0x3f3f3f3f;

int n, m;
int mat[maxn][maxm];
int link[maxm][maxn];
int vlink[maxm], vis[maxm], num[maxm];

inline bool scan_d(int& num)
{
    char in;
    bool IsN = false;
    in = getchar();
    if (in == EOF)
        return false;
    while (in != '-' && (in < '0' || in > '9'))
        in = getchar();
    if (in == '-') {
        IsN = true;
        num = 0;
    } else
        num = in - '0';
    while (in = getchar(), in >= '0' && in <= '9') {
        num *= 10, num += in - '0';
    }
    if (IsN)
        num = -num;
    return true;
}

bool dfs(int u)
{
    each(v, m) if (mat[u][v] && !vis[v])
    {
        vis[v] = true;
        if (vlink[v] < num[v]) {
            link[v][vlink[v]++] = u;
            return true;
        }
        each(j, vlink[v]) if (dfs(link[v][j]))
        {
            link[v][j] = u;
            return true;
        }
    }
    return false;
}

bool hungary()
{
    fill(vlink, 0);
    each(i, n)
    {
        fill(vis, false);
        if (!dfs(i))
            return false;
    }
    return true;
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        each(i, n) each(j, m) scan_d(mat[i][j]);
        each(i, m) scan_d(num[i]);
        if (hungary())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}
多重匹配

POJ 3189 Steady Cow Assignment

Posted on

二分图多重匹配第二题,提前再说一句,二分图匹配用网络流均可解
因为受了ysk学长博客的影响,开始习惯用宏定义写代码,有点不习惯,搞得我在控制范围上浪费了一些时间。

题意:
n头牛,m个牛棚,每头牛各自有各自喜欢的牛棚,给出喜欢的牛棚顺序,每个牛棚容量,要求他们的喜欢范围最小。(就是所住牛棚的最大喜欢值 - 最小喜欢值 最小)

思路:
二分牛棚数 ,并枚举范围起点,判断可行性 这么暴力?

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = (n - 1); (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (st) <= (en); (st)++)
#define rrange(i, st, en) for (int(i) = (st); (st) >= (en); (st)--)
#define fill(ary, num) memset((ary), (num), sizeof((ary)))

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1010;
const int maxm = 30;
int n, m, maxcap;
bool vis[maxn];
int link[maxm][maxn], vlink[maxm], mat[maxn][maxm], num[maxm];

bool dfs(int u, int st)
{
    each(i, m) if (i >= st && i < maxcap + st)
    {
        int v = mat[u][i] - 1;
        if (vis[v])
            continue;
        vis[v] = true;
        if (vlink[v] < num[v]) {
            link[v][vlink[v]++] = u;
            return true;
        }
        each(j, vlink[v]) if (dfs(link[v][j], st))
        {
            link[v][j] = u;
            return true;
        }
    }
    return false;
}

bool hungary(int mid)
{
    maxcap = mid;
    each(st, m - mid + 1)
    {
        fill(vlink, 0);
        bool flag = true;
        each(i, n)
        {
            fill(vis, false);
            if (!dfs(i, st)) {
                flag = false;
                break;
            }
        }
        if (flag)
            return true;
    }
    return false;
}

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        each(i, n)
            each(j, m)
                scanf("%d", &mat[i][j]);
        each(i, m)
            scanf("%d", &num[i]);
        int l = 1, r = m, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (hungary(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}
多重匹配

POJ 2289 Jamie’s Contact Groups

Posted on

最近网络流有点写累了,就尝试着写了一下二分图。
这是我第一道二分图多重匹配的题目,基本上是看着模板敲的……
因为中间在main函数内外都定义了n,m ,搞得我debug了好久……

二分图多重匹配想比喻二分图单匹配来说,只是多加了几步,本质上还是一样的。基本上看代码就能看懂。

题意:
有个女神的备胎很多,每次找备胎都很麻烦,搞得她很困扰。现在女神想把他的备胎们分成m组,根据关系有的必须放在特别的组,但是女神数学不好,于是女神随手找了个备胎帮助计算,在满足条件的情况下有个组内人数max,现在要你求最小的max。

思路:
二分人数+多重匹配。
最大流也可。二分到汇点的容量即可。

这里有个小麻烦,就是有不定数量的数字。
一般人会立马想到,最麻烦的getchar() , 好一点的想到 stringstream
这里比较合适的应该是 一起输入一个数字和字符,如果字符是换行符号则退出。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <sstream>
#include <string>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define fill(ary, num) memset((ary), (num), sizeof((ary)))

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1010;
int n, m, maxcap;
bool vis[maxn], g[maxn][maxn];
int link[maxn][maxn], vlink[maxn];
char buf[60];

bool dfs(int u)
{
    each(i, m) if (g[u][i] && !vis[i])
    {
        vis[i] = true;
        if (vlink[i] < maxcap) {
            link[i][vlink[i]++] = u;
            return true;
        }
        each(j, vlink[i]) if (dfs(link[i][j]))
        {
            link[i][j] = u;
            return true;
        }
    }
    return false;
}

bool hungary(int mid)
{
    maxcap = mid;
    fill(vlink, 0);
    each(i, n)
    {
        fill(vis, false);
        if (!dfs(i))
            return false;
    }
    return true;
}

inline void input(int u)
{
    int a;
    char c;
    scanf("%s", buf);
    while (true) {
        scanf("%d%c", &a, &c);
        g[u][a] = true;
        if (c == '\n')
            break;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    while (scanf("%d %d", &n, &m) != EOF && (n || m)) {
        fill(g, false);
        each(i, n) input(i);
        int l = 1, r = n, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (hungary(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        printf("%d\n", r + 1);
    }
    return 0;
}
带权最大匹配

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;
}