DQS DQS

HIT Summer Training Day11 匈牙利|KM

in 算法,匈牙利算法&&KM算法,图论,模拟赛read (89) 文章转载请注明来源!

二分图和网络流姿势还是需要提高,菜的抠脚


A : hdu - 1083

一堆人选课,每个课有一个学生的集合,一个课只能有一个学生,一个学生只能上一个课。问P个课是否能被全选。

裸的二分图匹配

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 100010;
const int INF = 1000000010ll;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int head[710],nxt[SZ],to[SZ],tot = 1;

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

int match[710];
bool vis[710];
bool dfs(int u)
{
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!vis[v])
        {
            vis[v] = 1;
            if(!match[v] || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;

}

int main()
{
    int T = read();
    while(T --)
    {
        memset(head,0,sizeof(head)); tot = 1;
        memset(match,0,sizeof(match));
        int nl = read(),nr = read();
    //    if(nl != nr) { puts("NO"); continue; }
        int n = nl + nr;
        for(int i = 1;i <= nl;i ++)
        {
            int k = read(),x;
            while(k --)
                x = read(),build(i,x + nl);
        }
        int ans = 0;
        for(int i = 1;i <= n;i ++)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ans ++;
        }
        if(ans == nl) puts("YES");
        else puts("NO");
    }
    return 0;
}


B : hdu - 2063

裸的找cp。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 10010;
const int INF = 1000000010ll;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int head[SZ],nxt[SZ],to[SZ],tot = 1;

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

int match[SZ];
bool vis[SZ];
bool dfs(int u)
{
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!vis[v])
        {
            vis[v] = 1;
            if(!match[v] || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;

}

int main()
{
    int k,nl,nr;
    while(~scanf("%d",&k) && k)
    {
        memset(head,0,sizeof(head)); tot = 1;
        memset(match,0,sizeof(match));
        nl = read(),nr = read();
        int n = nl + nr;
        for(int i = 1;i <= k;i ++)
        {
            int x = read(),y = read(); y += n;
            build(x,y);
        }
        int ans = 0;
        for(int i = 1;i <= n;i ++)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ans ++;
        }
        printf("%d\n",ans);
    }
    return 0;
}


C : hdu - 2819

给一个01矩阵,问能否通过交换行和列使其变成一条对角线全为1。能则输出交换方案。

仔细思考发现可以只交换行或者只交换列来达到……

于是可以对当前行向某个行连边表示做一个交换。最大匹配等于n说明有解。

需要注意交换后第i行就不是第i行了……超坑

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 100010;
const int INF = 1000000010ll;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int head[710],nxt[SZ],to[SZ],tot = 1;

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

int match[710];
bool vis[710];
bool dfs(int u)
{
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!vis[v])
        {
            vis[v] = 1;
            if(!match[v] || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;

}

int xx[SZ],yy[SZ];
int a[710][710];

bool use[SZ];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        memset(head,0,sizeof(head)); tot = 1;
        memset(match,0,sizeof(match));
        memset(use,0,sizeof(use));
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                scanf("%d",&a[i][j]);
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                if(a[i][j])
                    build(i,j);
        int ans = 0;
        for(int i = 1;i <= n;i ++)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ans ++;
        }
        if(ans != n) { puts("-1"); continue; }
        int t = 0;

    //    for(int i = 1;i <= n;i ++)    cout << match[i] << " "; puts("");

        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= n;j ++)
            {
                if(i != j && match[j] == i)
                {
                    xx[++ t] = i,yy[t] = j;
                    swap(match[i],match[j]);
                    break;
                }
            }
        }
        printf("%d\n",t);
        for(int i = 1;i <= t;i ++)
            printf("C %d %d\n",xx[i],yy[i]);
    }
    return 0;
}
/*
3
0 0 1
1 0 0
0 1 1

*/


D : hdu - 5093

给一张地图,可以放船放在*上,两只船不能在同一行或者同一列,除非中间有#隔开。问最多放多少船。

将连续的、被#隔开的一行和一列看做一个点,如果一行和一列相交则连边,表示可以放一个点。

可以发现一个点只能被覆盖一次,这样就是选择最多的边使其两两没有公共点,即最大匹配。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010ll;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

char maps[1010][1010];

int head[SZ],nxt[SZ],to[SZ],tot = 1;

int x[1010][1010],y[1010][1010],totp = 1;

void build(int f,int t)
{
    to[++ tot] = t;
    nxt[tot] = head[f];
    head[f] = tot;
}

int match[SZ];
bool vis[SZ];
bool dfs(int u)
{
    for(int i = head[u];i;i = nxt[i])
    {
        int v = to[i];
        if(!vis[v])
        {
            vis[v] = 1;
            if(!match[v] || dfs(match[v]))
            {
                match[v] = u;
                return true;
            }
        }
    }
    return false;

}

int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        totp = 1; memset(head,0,sizeof(head)); tot = 1;
        memset(match,0,sizeof(match));
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        memset(maps,0,sizeof(maps));

        int n,m;
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i ++)
            scanf("%s",maps[i] + 1);
        for(int i = 1;i <= n;i ++)
        {
            for(int j = 1;j <= m;j ++)
            {
                if(maps[i][j] != '#')
                    x[i][j] = totp;
                else if(maps[i][j - 1] != '#')
                    totp ++;
            }
            if(maps[i][m] != '#') totp ++;
        }
        for(int j = 1;j <= m;j ++)
        {
            for(int i = 1;i <= n;i ++)
            {
                if(maps[i][j] != '#')
                    y[i][j] = totp;
                else if(maps[i - 1][j] != '#')
                    totp ++;
            }
            if(maps[n][j] != '#') totp ++;
        }
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
                if(maps[i][j] == '*')
                    build(x[i][j],y[i][j]);
        int ans = 0;
        for(int i = 1;i <= totp;i ++)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ans ++;
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
1
4 4
#***
*#**
**#*
ooo#

*/


E : hdu - 2255

裸的最大权匹配,KM算法。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;
 
typedef int LL;
const int SZ = 410;
const int INF = 1000000010ll;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}
 
int head[SZ],nxt[SZ],tot = 1;
 
struct edge
{
    int t; LL d;
}l[SZ];
 
void build(int f,int t,LL d)
{
    l[++ tot] = (edge){t,d};
    nxt[tot] = head[f];
    head[f] = tot;
}
 
 
int nl,nr,m,mat[SZ];
LL f[SZ][SZ];
LL lv[SZ],rv[SZ],rst[SZ];
bool visl[SZ],visr[SZ];
 
bool dfs(int u)
{
    visl[u] = 1;
    for(int v = 1;v <= nr;v ++)
    {
        if(visr[v]) continue;
        LL d = lv[u] + rv[v] - f[u][v];
        if(d == 0)
        {
            visr[v] = 1;
            if(!mat[v] || dfs(mat[v]))
                { mat[v] = u; return true; }
        }
        else
            rst[v] = min(rst[v],d);
    }
    return false;
}
 
 
 
LL KM()
{
    memset(mat,0,sizeof(mat));
    memset(rv,0,sizeof(rv));
    for(int i = 1;i <= nl;i ++)
    {
        lv[i] = f[i][1];
        for(int j = 2;j <= nr;j ++)
            lv[i] = max(lv[i],f[i][j]);
    }
    for(int x = 1;x <= nl;x ++)
    {
        fill(rst + 1,rst + 1 + nr,INF);
        while(233)
        {
            memset(visl,0,sizeof(visl));
            memset(visr,0,sizeof(visr));
            if(dfs(x)) break;
            LL d = INF;
            for(int i = 1;i <= nr;i ++)
                if(!visr[i]) d = min(d,rst[i]);
            for(int i = 1;i <= nl;i ++)
                if(visl[i]) lv[i] -= d;
            for(int i = 1;i <= nr;i ++)
                if(visr[i]) rv[i] += d;
                else rst[i] -= d;
        }
    }
    LL ans = 0;
    for(int i = 1;i <= nr;i ++)
        ans += f[mat[i]][i];
    return ans;
}
 
int ans[SZ];
 
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        nl = n,nr = n;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                f[i][j] = read();
        printf("%d\n",KM());
    }
 
    return 0;
}

F : hdu - 2282

给n个盒子排成一个环,每个盒子中有0个或若干个物品。每次操作只能将一个物品取出放到相邻的盒子中。问最少多少次操作可以让每个盒子中的物品数为1或者为0。保证有解。

每个物品当做一个点,朝向它最终可能在的盒子连边,长度为移动次数。

这样就是一个最小权匹配问题。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;
 
typedef long long LL;
const int SZ = 610;
const LL INF = 100000000000000010ll;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}
 
int head[SZ],nxt[SZ],tot = 1;
 
struct edge
{
    int t; LL d;
}l[SZ];
 
void build(int f,int t,LL d)
{
    l[++ tot] = (edge){t,d};
    nxt[tot] = head[f];
    head[f] = tot;
}
 
 
int n,m,mat[SZ];
LL f[SZ][SZ];
LL lv[SZ],rv[SZ],rst[SZ];
bool visl[SZ],visr[SZ];
 
bool dfs(int u)
{
    visl[u] = 1;
    for(int v = 1;v <= n;v ++)
    {
        if(visr[v]) continue;
        LL d = lv[u] + rv[v] - f[u][v];
        if(d == 0)
        {
            visr[v] = 1;
            if(!mat[v] || dfs(mat[v]))
                { mat[v] = u; return true; }
        }
        else
            rst[v] = min(rst[v],d);
    }
    return false;
}
 
 
 
LL KM()
{
    memset(rv,0,sizeof(rv));
    for(int i = 1;i <= n;i ++)
    {
        lv[i] = f[i][1];
        for(int j = 2;j <= n;j ++)
            lv[i] = max(lv[i],f[i][j]);
    }
    for(int x = 1;x <= n;x ++)
    {
        fill(rst + 1,rst + 1 + n,INF);
        while(233)
        {
            memset(visl,0,sizeof(visl));
            memset(visr,0,sizeof(visr));
            if(dfs(x)) break;
            LL d = INF;
            for(int i = 1;i <= n;i ++)
                if(!visr[i]) d = min(d,rst[i]);
            for(int i = 1;i <= n;i ++)
                if(visl[i]) lv[i] -= d;
            for(int i = 1;i <= n;i ++)
                if(visr[i]) rv[i] += d;
                else rst[i] -= d;
        }
    }
    LL ans = 0;
    for(int i = 1;i <= n;i ++)
        ans += f[mat[i]][i];
    return ans;
}
 
 
int a[SZ];
 
int main()
{
    while(~scanf("%d",&n))
    {
        memset(mat,0,sizeof(mat));
        memset(f,0,sizeof(f));
        for(int i = 1;i <= n;i ++) a[i] = read();
        int tot = 0;
        for(int i = 1;i <= n;i ++)
        {
            while(a[i])
            {
                a[i] --; tot ++;
                for(int j = 1;j <= n;j ++)
                    f[tot][j] = min(abs(i - j),n - abs(i - j));
            }
        }
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= n;j ++)
                f[i][j] *= -1;
        printf("%d\n",-KM());
    }
 
    return 0;
}

G : hdu - 2448

给一张m个点的带权图,其中有n个点上有船,有n个港口,问n个船一一对应走到n个港口所走的最少距离。

floyd预处理一下,就是KM裸题

题意有毒,半天看不懂

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef long long LL;
const int SZ = 410;
const LL INF = 100000000000000010ll;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}

int head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t; LL d;
}l[SZ];

void build(int f,int t,LL d)
{
    l[++ tot] = (edge){t,d};
    nxt[tot] = head[f];
    head[f] = tot;
}


int n,m,mat[SZ];
LL f[SZ][SZ];
LL lv[SZ],rv[SZ],rst[SZ];
bool visl[SZ],visr[SZ];

bool dfs(int u)
{
    visl[u] = 1;
    for(int v = 1;v <= n;v ++)
    {
        if(visr[v]) continue;
        LL d = lv[u] + rv[v] - f[u][v];
        if(d == 0)
        {
            visr[v] = 1;
            if(!mat[v] || dfs(mat[v]))
                { mat[v] = u; return true; }
        }
        else
            rst[v] = min(rst[v],d);
    }
    return false;
}



LL KM()
{
    memset(rv,0,sizeof(rv));
    for(int i = 1;i <= n;i ++)
    {
        lv[i] = f[i][1];
        for(int j = 2;j <= n;j ++)
            lv[i] = max(lv[i],f[i][j]);
    }
    for(int x = 1;x <= n;x ++)
    {
        fill(rst + 1,rst + 1 + n,INF);
        while(233)
        {
            memset(visl,0,sizeof(visl));
            memset(visr,0,sizeof(visr));
            if(dfs(x)) break;
            LL d = INF;
            for(int i = 1;i <= n;i ++)
                if(!visr[i]) d = min(d,rst[i]);
            for(int i = 1;i <= n;i ++)
                if(visl[i]) lv[i] -= d;
            for(int i = 1;i <= n;i ++)
                if(visr[i]) rv[i] += d;
                else rst[i] -= d;
        }
    }
    LL ans = 0;
    for(int i = 1;i <= n;i ++)
        ans += f[mat[i]][i];
    return ans;
}


LL floyd[SZ][SZ];
int s[SZ];

int main()
{
    int m,k,p;
    while(~scanf("%d%d%d%d",&n,&m,&k,&p))
    {
        for(int i = 1;i <= n;i ++) s[i] = read();
        memset(mat,0,sizeof(mat));
        memset(floyd,63,sizeof(floyd));
        memset(f,63,sizeof(f));
        for(int i = 1;i <= m;i ++) floyd[i][i] = 0;
        for(int i = 1;i <= k;i ++)
        {
            int x = read(),y = read();
            LL z = read();
            floyd[x][y] = floyd[y][x] = min(floyd[x][y],z);
        }

        for(int k = 1;k <= m;k ++)
            for(int i = 1;i <= m;i ++)
                for(int j = 1;j <= m;j ++)
                    floyd[i][j] = min(floyd[i][j],floyd[i][k]+floyd[k][j]);
    /*    for(int i = 1;i <= m;i ++,puts(""))
            for(int j = 1;j <= m;j ++)
                printf("%d ",floyd[i][j]);*/
        for(int i = 1;i <= p;i ++)
        {
            int x = read(),y = read();
            LL z = read();
            for(int j = 1;j <= n;j ++)
                f[j][x] = min(f[j][x],z + floyd[y][s[j]]);
        }
    /*    for(int i = 1;i <= n;i ++,puts(""))
            for(int j = 1;j <= n;j ++)
                f[i][j] *= -1,printf("%d ",f[i][j]);*/
            for(int i = 1;i <= n;i ++)
                for(int j = 1;j <= n;j ++)
                    f[i][j] *= -1;
        printf("%d\n",-KM());
    }

    return 0;
}
/*

*/


H : hdu - 2853

给一个匹配,问最少改变多少匹配可以使其变成最大权匹配。

一个很经典的思路都被我忘掉了……

每个权值都放大一个倍数,然后若想要让同边权的优先选某条边,就给他的边权+1。

需要保证+1不会影响其他边的选择,所以倍数要求要大一些。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<queue>
#include<stack>
using namespace std;

typedef int LL;
const int SZ = 100010;
const int INF = 100010;
const int mod = 1000000007;
LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a <= '9' && a >= '0') {n = n * 10 + a - '0'; a = getchar(); }
    if(flag) n = -n;
    return n;
}


int n,m,mat[60];
LL f[60][60];
LL lv[60],rv[60],rst[60];
bool visl[60],visr[60];

bool dfs(int u)
{
    visl[u] = 1;
    for(int v = 1;v <= n;v ++)
    {
        if(visr[v]) continue;
        LL d = lv[u] + rv[v] - f[u][v];
        if(d == 0)
        {
            visr[v] = 1;
            if(!mat[v] || dfs(mat[v]))
                { mat[v] = u; return true; }
        }
        else
            rst[v] = min(rst[v],d);
    }
    return false;
}



LL KM()
{
    memset(rv,0,sizeof(rv));
    for(int i = 1;i <= n;i ++)
    {
        lv[i] = f[i][1];
        for(int j = 2;j <= n;j ++)
            lv[i] = max(lv[i],f[i][j]);
    }
    for(int x = 1;x <= n;x ++)
    {
        fill(rst + 1,rst + 1 + n,INF);
        while(233)
        {
            memset(visl,0,sizeof(visl));
            memset(visr,0,sizeof(visr));
            if(dfs(x)) break;
            LL d = INF;
            for(int i = 1;i <= n;i ++)
                if(!visr[i]) d = min(d,rst[i]);
            for(int i = 1;i <= n;i ++)
                if(visl[i]) lv[i] -= d;
            for(int i = 1;i <= n;i ++)
                if(visr[i]) rv[i] += d;
                else rst[i] -= d;
        }
    }
    LL ans = 0;
    for(int i = 1;i <= n;i ++)
        ans += f[mat[i]][i];
    return ans;
}

int a[SZ],b[SZ];

int main()
{
    int nl,nr;
    while(~scanf("%d%d",&nl,&nr))
    {
        n = max(nl,nr);

        memset(mat,0,sizeof(mat));
        memset(f,0,sizeof(f));
        for(int i = 1;i <= nl;i ++)
            for(int j = 1;j <= nr;j ++)
                f[i][j] = read();
        LL sum = 0;
        for(int i = 1;i <= nl;i ++) a[i] = read(),sum += f[i][a[i]];
        LL maxn = KM();
        for(int i = 1;i <= nl;i ++)
            for(int j = 1;j <= nr;j ++)
                f[i][j] *= 1000;
        for(int i = 1;i <= nl;i ++) f[i][a[i]] ++;
        memset(mat,0,sizeof(mat));
        KM();
        int ans = 0;
        for(int i = 1;i <= nr;i ++) b[mat[i]] = i;
        for(int i = 1;i <= nl;i ++)
            if(b[i] != a[i]) ans ++;
        printf("%d %d\n",ans,maxn - sum);
    }

    return 0;
}
/*

*/

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法匈牙利算法&&KM算法图论模拟赛
最后由DQS修改于2017-08-14 20:36
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆