KM算法( 一 )

A - 奔小康賺大錢
題意：
求解二分圖的最優(yōu)匹配

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

using namespace std;
const int MAXN = 305;
const int INF = 0x3f3f3f3f;

int love[MAXN][MAXN];   // 記錄每個妹子和每個男生的好感度
int ex_girl[MAXN];      // 每個妹子的期望值
int ex_boy[MAXN];       // 每個男生的期望值
bool vis_girl[MAXN];    // 記錄每一輪匹配匹配過的女生
bool vis_boy[MAXN];     // 記錄每一輪匹配匹配過的男生
int match[MAXN];        // 記錄每個男生匹配到的妹子 如果沒有則為-1
int slack[MAXN];        // 記錄每個漢子如果能被妹子傾心最少還需要多少期望值

int N;


bool dfs(int girl)
{
    vis_girl[girl] = true;

    for (int boy = 0; boy < N; ++boy) {

        if (vis_boy[boy]) continue; // 每一輪匹配 每個男生只嘗試一次

        int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];

        if (gap == 0) {  // 如果符合要求
            vis_boy[boy] = true;
            if (match[boy] == -1 || dfs( match[boy] )) {    // 找到一個沒有匹配的男生 或者該男生的妹子可以找到其他人
                match[boy] = girl;
                return true;
            }
        } else {
            slack[boy] = min(slack[boy], gap);  // slack 可以理解為該男生要得到女生的傾心 還需多少期望值 取最小值 備胎的樣子【捂臉
        }
    }

    return false;
}

int KM()
{
    memset(match, -1, sizeof match);    // 初始每個男生都沒有匹配的女生
    memset(ex_boy, 0, sizeof ex_boy);   // 初始每個男生的期望值為0

    // 每個女生的初始期望值是與她相連的男生最大的好感度
    for (int i = 0; i < N; ++i) {
        ex_girl[i] = love[i][0];
        for (int j = 1; j < N; ++j) {
            ex_girl[i] = max(ex_girl[i], love[i][j]);
        }
    }

    // 嘗試為每一個女生解決歸宿問題
    for (int i = 0; i < N; ++i) {

        fill(slack, slack + N, INF);    // 因為要取最小值 初始化為無窮大

        while (1) {
            // 為每個女生解決歸宿問題的方法是 ：如果找不到就降低期望值，直到找到為止

            // 記錄每輪匹配中男生女生是否被嘗試匹配過
            memset(vis_girl, false, sizeof vis_girl);
            memset(vis_boy, false, sizeof vis_boy);

            if (dfs(i)) break;  // 找到歸宿 退出

            // 如果不能找到 就降低期望值
            // 最小可降低的期望值
            int d = INF;
            for (int j = 0; j < N; ++j)
                if (!vis_boy[j]) d = min(d, slack[j]);

            for (int j = 0; j < N; ++j) {
                // 所有訪問過的女生降低期望值
                if (vis_girl[j]) ex_girl[j] -= d;

                // 所有訪問過的男生增加期望值
                if (vis_boy[j]) ex_boy[j] += d;
                // 沒有訪問過的boy 因為girl們的期望值降低弟疆，距離得到女生傾心又進了一步钧排！
                else slack[j] -= d;
            }
        }
    }

    // 匹配完成 求出所有配對的好感度的和
    int res = 0;
    for (int i = 0; i < N; ++i)
        res += love[ match[i] ][i];

    return res;
}
int main()
{
    while (~scanf("%d", &N)) {

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                scanf("%d", &love[i][j]);

        printf("%d\n", KM());
    }
    return 0;
}

B - Going Home
題意:
給你一個N行M列的矩陣括勺，其中“.”代表空地灯谣，“H”代表房子潜秋，“m”代表人，其中有n個房子和n個人√バ恚現(xiàn)在要求每個人進入一間房子峻呛，且人走一步需要支付1美元。
求最小需要花費多少美元才能讓所有人都進入到房子中（每個人只能進入一間房子辜窑，每個房子只能容納一個人）杀饵。
題解:
每個人都與每個房間連接一條邊,邊權為水平距離加豎直距離,然后得到一個二分圖,對這個二分圖運用KM算法.

#include <iostream>
#include <cstring>
#include <cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN = 210;
const int INF = 0x3f3f3f3f;
int love[MAXN][MAXN];   // 記錄每個妹子和每個男生的好感度
int ex_girl[MAXN];      // 每個妹子的期望值
int ex_boy[MAXN];       // 每個男生的期望值
bool vis_girl[MAXN];    // 記錄每一輪匹配匹配過的女生
bool vis_boy[MAXN];     // 記錄每一輪匹配匹配過的男生
int match[MAXN];        // 記錄每個男生匹配到的妹子 如果沒有則為-1
int slack[MAXN];        // 記錄每個漢子如果能被妹子傾心最少還需要多少期望值
int N;
struct Node
{
    int x,y;
};
Node xc[MAXN],yc[MAXN];
bool dfs(int girl)
{
    vis_girl[girl] = true;
    for (int boy = 0; boy < N; ++boy) {
        if (vis_boy[boy]) continue; // 每一輪匹配 每個男生只嘗試一次
        int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
        if (gap == 0) {  // 如果符合要求
            vis_boy[boy] = true;
            if (match[boy] == -1 || dfs( match[boy] )) {    // 找到一個沒有匹配的男生 或者該男生的妹子可以找到其他人
                match[boy] = girl;
                return true;
            }
        } else {
            slack[boy] = min(slack[boy], gap);  // slack 可以理解為該男生要得到女生的傾心 還需多少期望值 取最小值 備胎的樣子【捂臉
        }
    }
    return false;
}
int KM()
{
    memset(match, -1, sizeof match);    // 初始每個男生都沒有匹配的女生
    memset(ex_boy, 0, sizeof ex_boy);   // 初始每個男生的期望值為0
    // 每個女生的初始期望值是與她相連的男生最大的好感度
    for (int i = 0; i < N; ++i) {
        ex_girl[i] = love[i][0];
        for (int j = 1; j < N; ++j) {
            ex_girl[i] = max(ex_girl[i], love[i][j]);
        }
    }
    // 嘗試為每一個女生解決歸宿問題
    for (int i = 0; i < N; ++i) {
        fill(slack, slack + N, INF);    // 因為要取最小值 初始化為無窮大
        while (1) {
            // 為每個女生解決歸宿問題的方法是 ：如果找不到就降低期望值，直到找到為止
            // 記錄每輪匹配中男生女生是否被嘗試匹配過
            memset(vis_girl, false, sizeof vis_girl);
            memset(vis_boy, false, sizeof vis_boy);
            if (dfs(i)) break;  // 找到歸宿 退出
            // 如果不能找到 就降低期望值
            // 最小可降低的期望值
            int d = INF;
            for (int j = 0; j < N; ++j)
                if (!vis_boy[j]) d = min(d, slack[j]);
            for (int j = 0; j < N; ++j) {
                // 所有訪問過的女生降低期望值
                if (vis_girl[j]) ex_girl[j] -= d;

                // 所有訪問過的男生增加期望值
                if (vis_boy[j]) ex_boy[j] += d;
                // 沒有訪問過的boy 因為girl們的期望值降低谬擦，距離得到女生傾心又進了一步！
                else slack[j] -= d;
            }
        }
    }
    // 匹配完成 求出所有配對的好感度的和
    int res = 0;
    for (int i = 0; i < N; ++i)
        res += love[ match[i] ][i];
    return res;
}
int main()
{
    int n,m,sum1,sum2;
    char c;
    while(scanf("%d%d",&n,&m)!=EOF,n+m)
    {
        sum1=0;
        sum2=0;
        getchar();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                c=getchar();
                if(c=='m')
                {
                    xc[sum1].x=i;
                    xc[sum1++].y=j;
                }
                else if(c=='H')
                {
                    yc[sum2].x=i;
                    yc[sum2++].y=j;
                }
            }
            c=getchar();
        }
        for(int i=0;i<sum1;i++)
        {
            for(int j=0;j<sum2;j++)
            {
                love[i][j]=-abs(xc[i].x-yc[j].x)-abs(xc[i].y-yc[j].y);
            }
        }
        N=sum1;
        printf("%d\n",-KM());
    }
    return 0;
}

C - Interesting Housing Problem
題意:
現(xiàn)在有1所學校朽缎，N個學生,M個公寓惨远，還有一個R值，代表學生對該公寓的滿意度话肖，如果為正數(shù)北秽，越高表示越喜歡住在該所公寓，0表示不喜歡也不討厭（意思就是可以鬃钔病）贺氓，如果為負數(shù)則代表不喜歡住，也不能状仓（要不小心起義~）≌夼啵現(xiàn)在校長想讓所有學生的滿意度最高，而且學生跟公寓是一一對應的邢锯，另外扬蕊，學生也不能入住那些沒對公寓進行評價的。
求出最大值丹擎。
題解:

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

using namespace std;
const int MAXN = 510;
const int INF = 0x3f3f3f3f;

int love[MAXN][MAXN];   // 記錄每個妹子和每個男生的好感度
int ex_girl[MAXN];      // 每個妹子的期望值
int ex_boy[MAXN];       // 每個男生的期望值
bool vis_girl[MAXN];    // 記錄每一輪匹配匹配過的女生
bool vis_boy[MAXN];     // 記錄每一輪匹配匹配過的男生
int match[MAXN];        // 記錄每個男生匹配到的妹子 如果沒有則為-1
int slack[MAXN];        // 記錄每個漢子如果能被妹子傾心最少還需要多少期望值

int n,m;

struct Node
{
    int x,y;
};
Node xc[MAXN],yc[MAXN];
bool dfs(int girl)
{
    vis_girl[girl] = true;

    for (int boy = 0; boy < m; ++boy) {

        if (vis_boy[boy]) continue; // 每一輪匹配 每個男生只嘗試一次

        int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];

        if (gap == 0) {  // 如果符合要求
            vis_boy[boy] = true;
            if (match[boy] == -1 || dfs( match[boy] )) {    // 找到一個沒有匹配的男生 或者該男生的妹子可以找到其他人
                match[boy] = girl;
                return true;
            }
        } else {
            slack[boy] = min(slack[boy], gap);  // slack 可以理解為該男生要得到女生的傾心 還需多少期望值 取最小值 備胎的樣子【捂臉
        }
    }

    return false;
}

int KM()
{
    memset(match, -1, sizeof match);    // 初始每個男生都沒有匹配的女生
    memset(ex_boy, 0, sizeof ex_boy);   // 初始每個男生的期望值為0

    // 每個女生的初始期望值是與她相連的男生最大的好感度
    for (int i = 0; i < n; ++i) {
        ex_girl[i] = love[i][0];
        for (int j = 1; j < m; ++j) {
            ex_girl[i] = max(ex_girl[i], love[i][j]);
        }
    }

    // 嘗試為每一個女生解決歸宿問題
    for (int i = 0; i < n; ++i) {

        fill(slack, slack + m, INF);    // 因為要取最小值 初始化為無窮大

        while (1) {
            // 為每個女生解決歸宿問題的方法是 ：如果找不到就降低期望值尾抑，直到找到為止

            // 記錄每輪匹配中男生女生是否被嘗試匹配過
            memset(vis_girl, false, sizeof vis_girl);
            memset(vis_boy, false, sizeof vis_boy);

            if (dfs(i)) break;  // 找到歸宿 退出

            // 如果不能找到 就降低期望值
            // 最小可降低的期望值
            int d = INF;
            for (int j = 0; j < m; ++j)
                if (!vis_boy[j]) d = min(d, slack[j]);
            if(d==INF) return -1;  //無法松弛,找不到完備匹配
            for (int j = 0; j < n; ++j) {
                // 所有訪問過的女生降低期望值
                if (vis_girl[j]) ex_girl[j] -= d;
            }

            for (int j = 0; j < m; ++j) {
                // 所有訪問過的男生增加期望值
                if (vis_boy[j]) ex_boy[j] += d;
                // 沒有訪問過的boy 因為girl們的期望值降低歇父，距離得到女生傾心又進了一步！
                else slack[j] -= d;
            }
        }
    }

    // 防止匹配到不存在的邊
    int res = 0,flag=0;
    for(int i = 0; i < m; i++){
        if(match[i]==-1||love[match[i]][i]==-INF)
            continue;
        res += love[match[i]][i];
        flag++;
    }
    if(flag<n) res=-1;
    return res;
}
int main()
{
    int a,b,c,e,cas=1;
    while(scanf("%d%d%d",&n,&m,&e)!=EOF){
        for(int i=0;i<n;i++)
         for(int j=0;j<m;j++)
             love[i][j]=-INF;
        for(int i=0;i<e;i++) {
            scanf("%d%d%d",&a,&b,&c);
            if(c<0)  continue;
            love[a][b]=c;
        }
        printf("Case %d: %d\n",cas++,KM());
    }
    return 0;
}

D - Special Fish
題意:
武大荷塘有N條魚(不分性別),每條魚有一個價值vi.且給出一個N*N的矩陣,矩陣中(i,j)格為1表示,第i條魚會攻擊第j條魚并產(chǎn)下卵.
產(chǎn)卵的數(shù)量= vi XOR vj. 現(xiàn)在每條魚只能被攻擊1次(一條魚只能攻擊1次且被攻擊1次),且每條魚只會攻擊它可能會攻擊的所有魚中的一條(哪些其他魚它會攻擊已經(jīng)在N*N矩陣中給出).現(xiàn)在要你求這N條魚產(chǎn)卵數(shù)目的最大值.
題解:

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

using namespace std;
const int MAXN = 110;
const int INF = 0x3f3f3f3f;

int love[MAXN][MAXN];   // 記錄每個妹子和每個男生的好感度
int ex_girl[MAXN];      // 每個妹子的期望值
int ex_boy[MAXN];       // 每個男生的期望值
bool vis_girl[MAXN];    // 記錄每一輪匹配匹配過的女生
bool vis_boy[MAXN];     // 記錄每一輪匹配匹配過的男生
int match[MAXN];        // 記錄每個男生匹配到的妹子 如果沒有則為-1
int slack[MAXN];        // 記錄每個漢子如果能被妹子傾心最少還需要多少期望值

int val[MAXN];
int N;

struct Node
{
    int x,y;
};
Node xc[MAXN],yc[MAXN];
bool dfs(int girl)
{
    vis_girl[girl] = true;

    for (int boy = 0; boy < N; ++boy) {

        if (vis_boy[boy]) continue; // 每一輪匹配 每個男生只嘗試一次

        int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];

        if (gap == 0) {  // 如果符合要求
            vis_boy[boy] = true;
            if (match[boy] == -1 || dfs( match[boy] )) {    // 找到一個沒有匹配的男生 或者該男生的妹子可以找到其他人
                match[boy] = girl;
                return true;
            }
        } else {
            slack[boy] = min(slack[boy], gap);  // slack 可以理解為該男生要得到女生的傾心 還需多少期望值 取最小值 備胎的樣子【捂臉
        }
    }

    return false;
}

int KM()
{
    memset(match, -1, sizeof match);    // 初始每個男生都沒有匹配的女生
    memset(ex_boy, 0, sizeof ex_boy);   // 初始每個男生的期望值為0

    // 每個女生的初始期望值是與她相連的男生最大的好感度
    for (int i = 0; i < N; ++i) {
        ex_girl[i] = love[i][0];
        for (int j = 1; j < N; ++j) {
            ex_girl[i] = max(ex_girl[i], love[i][j]);
        }
    }

    // 嘗試為每一個女生解決歸宿問題
    for (int i = 0; i < N; ++i) {

        fill(slack, slack + N, INF);    // 因為要取最小值 初始化為無窮大

        while (1) {
            // 為每個女生解決歸宿問題的方法是 ：如果找不到就降低期望值再愈，直到找到為止

            // 記錄每輪匹配中男生女生是否被嘗試匹配過
            memset(vis_girl, false, sizeof vis_girl);
            memset(vis_boy, false, sizeof vis_boy);

            if (dfs(i)) break;  // 找到歸宿 退出

            // 如果不能找到 就降低期望值
            // 最小可降低的期望值
            int d = INF;
            for (int j = 0; j < N; ++j)
                if (!vis_boy[j]) d = min(d, slack[j]);

            for (int j = 0; j < N; ++j) {
                // 所有訪問過的女生降低期望值
                if (vis_girl[j]) ex_girl[j] -= d;

                // 所有訪問過的男生增加期望值
                if (vis_boy[j]) ex_boy[j] += d;
                // 沒有訪問過的boy 因為girl們的期望值降低榜苫，距離得到女生傾心又進了一步！
                else slack[j] -= d;
            }
        }
    }

    // 匹配完成 求出所有配對的好感度的和
    int res = 0;
    for (int i = 0; i < N; ++i)
        res += love[ match[i] ][i];

    return res;
}
int main()
{
    while(scanf("%d",&N)!=EOF,N)
    {
        for(int i=0;i<N;i++)
            scanf("%d",val+i);
        memset(love,0,sizeof(love));
        char c;
        for(int i=0;i<N;i++)
        {
            for(int j=0;j<N;j++)
            {
                scanf(" %c",&c);
                if(c=='1')
                {
                    love[i][j]=val[i]^val[j];
                }
            }
        }
        printf("%d\n",KM());
    }

    return 0;
}

S - Ants
題意:
跟B題差不多,給定n個蟲的坐標和m顆樹的坐標(m>n),n個從要搬遷到樹中,每棵樹只能住一個蟲翎冲。求出搬遷的最短距離垂睬。
題解:
兩點距離直接算就可以了,蟲樹兩兩之間連邊,權值可能是小數(shù),所以要控制浮點誤差eps

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;
const int MAXN=110;
const int INF=0x3f3f3f3f;
double love[MAXN][MAXN],slack[MAXN];
int match[MAXN],ans[MAXN];
int visb[MAXN],visg[MAXN];
double eb[MAXN],eg[MAXN];
int n;
double eps=1e-10;
bool DFS(int girl)
{
    visg[girl]=true;
    for(int boy=1;boy<=n;boy++)
    {
        if(visb[boy]) continue;
        double gap=abs(eb[boy]+eg[girl]-love[girl][boy]);
        if(gap<=eps)
        {
            visb[boy]=1;
            if(match[boy]==-1||DFS(match[boy]))
            {
                match[boy]=girl;
                return true;
            }
        }
        else slack[boy]=min(slack[boy],gap);
    }
    return false;
}
void km()
{
    memset(match,-1,sizeof(match));
    memset(eb,0,sizeof(eb));
    for(int i=1;i<=n;i++)
    {
        eg[i]=love[i][1];
        for(int j=2;j<=n;j++)
        {
            eg[i]=max(eg[i],love[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        fill(slack+1,slack+1+n,INF);
        while(true)
        {
            memset(visg,0,sizeof(visg));
            memset(visb,0,sizeof(visb));
            if(DFS(i)) break;
            double d=INF;
            for(int i=1;i<=n;i++)
            {
                if(!visb[i]) d=min(d,slack[i]);
            }
            for(int i=1;i<=n;i++)
            {
                if(visg[i]) eg[i]-=d;
                if(visb[i]) eb[i]+=d;
                else slack[i]-=d;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",match[i]);
    }
}
double dist(pair<double,double> p1,pair<double,double> p2)
{
    return -sqrt((p1.first-p2.first)*(p1.first-p2.first)+(p1.second-p2.second)*(p1.second-p2.second));
}
pair<double,double>  worm[MAXN];
pair<double,double> tree[MAXN];
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&worm[i].first,&worm[i].second);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&tree[i].first,&tree[i].second);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                love[i][j]=dist(tree[i],worm[j]);
            }
        }
        km();
    }
}

E - Chocolate
題意:
有n個盒子組成一個圓，盒子總共有不超過n個蛋糕府适，有的有多于1個羔飞，有的為0￠艽海可以將一個盒子里的蛋糕往左右兩個盒子里移動逻淌，一次只能移動一個，使最終每個盒子里有不超過一個蛋糕（可以沒有）疟暖，求最小的移動數(shù)
題解:
要使得每個盒子的蛋糕最多為一個,那么那些多于一個蛋糕的蛋糕盒里的蛋糕只能移向沒有蛋糕的蛋糕盒;也就是多出的蛋糕和空蛋糕盒構成二分圖,他們的距離為蛋糕盒之間的距離,由于是排列是圓形的,所以考慮另一個方向的距離

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

    using namespace std;
    const int MAXN = 510;
    const int INF = 0x3f3f3f3f;

    int love[MAXN][MAXN];
    int ex_girl[MAXN];
    int ex_boy[MAXN];
    bool vis_girl[MAXN];
    bool vis_boy[MAXN];
    int match[MAXN];
    int slack[MAXN];

    int N,M;

    bool dfs(int girl)
    {
        vis_girl[girl] = true;

        for (int boy = 0; boy < M; ++boy) {

            if (vis_boy[boy]) continue;

            int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];

            if (gap == 0) {
                vis_boy[boy] = true;
                if (match[boy] == -1 || dfs( match[boy] )) {
                    match[boy] = girl;
                    return true;
                }
            } else {
                slack[boy] = min(slack[boy], gap);
            }
        }

        return false;
    }

    int KM()
    {
        memset(match, -1, sizeof match);
        memset(ex_boy, 0, sizeof ex_boy);

        for (int i = 0; i < N; ++i) {
            ex_girl[i] = love[i][0];
            for (int j = 1; j < M; ++j) {
                ex_girl[i] = max(ex_girl[i], love[i][j]);
            }
        }


        for (int i = 0; i < N; ++i) {

            fill(slack, slack + M, INF);

            while (1) {
                memset(vis_girl, false, sizeof vis_girl);
                memset(vis_boy, false, sizeof vis_boy);

                if (dfs(i)) break;

                int d = INF;
                for (int j = 0; j < M; ++j)
                    if (!vis_boy[j]) d = min(d, slack[j]);

                for (int j = 0; j < N; ++j) {
                    if (vis_girl[j]) ex_girl[j] -= d;
                }
                for(int j=0;j<M;j++)
                {
                    if(vis_boy[j]) ex_boy[j]+=d;
                    else slack[j]-=d;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < M; ++i)
        {
            if(match[i]==-1||love[match[i]][i]==-INF) continue;
            res += love[ match[i] ][i];
        }
        return res;
    }
    int main()
    {
        while(scanf("%d",&N)!=EOF)
        {
            if(N==0) break;
            int val[MAXN];
            for(int i=0;i<N;i++)
            {
                scanf("%d",&val[i]);
            }
            int index[MAXN];
            int box=0;
            for(int i=0;i<N;i++)
            {
                if(!val[i]) index[box++]=i;
            }
            int cnt=0;
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<N;j++)
                {
                    love[i][j]=-INF;
                }
            }
            for(int i=0;i<N;i++)
            {
                if(val[i]>1)
                {
                    for(int j=1;j<val[i];j++)
                    {
                        for(int k=0;k<box;k++)
                        {
                            love[cnt][k]=-min(abs(index[k]-i),N-abs(index[k]-i));
                        }
                        cnt++;
                    }
                }
            }
            N=cnt;
            M=box;
            printf("%d\n",-KM());
        }
        return 0;
    }

F - One fihgt one
題意;
呂布和曹操對戰(zhàn)卡儒，給出兩隊的對戰(zhàn)情況，要求呂布傷害最小俐巴，即求最小權匹配
題解:
這里用到了map<string,int>,第一次知道插入map的key不單單是用string,還可以是char數(shù)組

    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include<cmath>
    #include<algorithm>
    #include<string>
    #include<map>
    using namespace std;
    const int MAXN = 205;
    const int INF = 0x3f3f3f3f;
    int love[MAXN][MAXN];
    int ex_girl[MAXN];
    int ex_boy[MAXN];
    bool vis_girl[MAXN];
    bool vis_boy[MAXN];
    int match[MAXN];
    int slack[MAXN];
    int N,M;
    bool dfs(int girl)
    {
        vis_girl[girl] = true;
        for (int boy = 0; boy < M; ++boy) {
            if (vis_boy[boy]) continue;
            int gap = ex_girl[girl] + ex_boy[boy] - love[girl][boy];
            if (gap == 0) {
                vis_boy[boy] = true;
                if (match[boy] == -1 || dfs( match[boy] )) {
                    match[boy] = girl;
                    return true;
                }
            } else {
                slack[boy] = min(slack[boy], gap);
            }
        }
        return false;
    }
    int KM()
    {
        memset(match, -1, sizeof match);
        memset(ex_boy, 0, sizeof ex_boy);
        for (int i = 0; i < N; ++i) {
            ex_girl[i] = love[i][0];
            for (int j = 1; j < M; ++j) {
                ex_girl[i] = max(ex_girl[i], love[i][j]);
            }
        }
        for (int i = 0; i < N; ++i) {
            fill(slack, slack + M, INF);
             while (1) {
                memset(vis_girl, false, sizeof vis_girl);
                memset(vis_boy, false, sizeof vis_boy);
                if (dfs(i)) break;
                int d = INF;
                for (int j = 0; j < M; ++j)
                    if (!vis_boy[j]) d = min(d, slack[j]);

                for (int j = 0; j < N; ++j) {
                    if (vis_girl[j]) ex_girl[j] -= d;
                }
                for(int j=0;j<M;j++)
                {
                    if(vis_boy[j]) ex_boy[j]+=d;
                    else slack[j]-=d;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < M; ++i)
        {
            if(match[i]==-1||love[match[i]][i]==-INF) continue;
            res += love[ match[i] ][i];
        }
        return res;
    }
    int main()
    {
        int T;
        int hurt;
        int index1,index2;
        char name1[25];
        char name2[25];
        int x,y;
        while(scanf("%d%d%d",&N,&M,&T)!=EOF)
        {
            map<string,int> lv,cao;
            index1=0;
            index2=0;
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<M;j++)
                {
                    love[i][j]=-INF;
                }
            }
            while(T--)
            {
                scanf("%s%s%d",name1,name2,&hurt);
                map<string,int>::iterator it;
                it=lv.find(name1);
                if(it==lv.end())
                {
                    x=index1;
                    lv[name1]=index1++;
                }
                else x=it->second;
                it=cao.find(name2);
                if(it==cao.end())
                {
                    y=index2;
                    cao[name2]=index2++;
                }
                else y=it->second;
                love[x][y]=-hurt;
            }
            printf("%d\n",-KM());
        }
        return 0;
    }

P - Going Home
題意:
這題和B題一樣的,代碼就不貼了
Q - Supervisor, Supervisee
題意:
n個雇員和n個雇主,給出n個雇員對每個雇主的評價(越低分越滿意),同樣給出n個雇主對每個雇員的評價(越低分越滿),求出匹配方案使得總滿意度最高(分數(shù)最低)骨望。如果存在多種方案,輸出所有的方案。
題解: ( 雙匹配邊 + 輸出所有合理方案 )
這題出現(xiàn)了雙邊,即匹配的雙方都有各自的看法,但是其實還是一樣的,只要建圖兩次,兩次的滿意度加在一起就可以了,然后求最小權匹配欣舵。
至于輸出多種方案:因為0 < N < 15,N比較小,我們先求出最小權匹配的ans,然后再對雇員進行全排列,每個雇主與之匹配,檢測匹配值是否等于ans,等于再輸出相應的方案擎鸠。注意:dfs進行全排列的時候,需要剪枝:如果當前積分比ans還要小(我套的是邊取負值,最大權匹配的模板),那就不要繼續(xù)走下去了,最后的方案一定不是對于ans的

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=20;
const int INF=0x3f3f3f3f;
int visb[MAXN],visg[MAXN];
int eboy[MAXN],egirl[MAXN];
int match[MAXN],slack[MAXN];
int love[MAXN][MAXN],n,res;
bool DFS(int girl)
{
    visg[girl]=1;
    for(int i=1;i<=n;i++)
    {
        if(visb[i]) continue;
        int gap=eboy[i]+egirl[girl]-love[girl][i];
        if(gap==0)
        {
            visb[i]=1;
            if(match[i]==-1||DFS(match[i]))
            {
                match[i]=girl;
                return true;
            }
        }
        else slack[i]=min(slack[i],gap);
    }
    return false;
}
void km()
{
    memset(eboy,0,sizeof(eboy));
    memset(match,-1,sizeof(match));
    for(int i=1;i<=n;i++)
    {
        egirl[i]=love[i][1];
        for(int j=2;j<=n;j++)
        {
            egirl[i]=max(egirl[i],love[i][j]);
        }
    }
    for(int i=1;i<=n;i++)
    {
        memset(slack,INF,sizeof(slack));
        while(true)
        {
            memset(visb,0,sizeof(visb));
            memset(visg,0,sizeof(visg));
            if(DFS(i)) break;
            int d=INF;
            for(int j=1;j<=n;j++)
            {
                if(!visb[j]) d=min(d,slack[j]);
            }
            for(int j=1;j<=n;j++)
            {
                if(visg[j]) egirl[j]-=d;

                if(visb[j]) eboy[j]+=d;
                else slack[j]-=d;
            }
        }
    }
    res=0;
    for(int i=1;i<=n;i++)
    {
        res+=love[match[i]][i];
    }
}
int num[MAXN],vis[MAXN],cnt,sum;
void km_dfs(int dept)//全排列
{
    if(sum<res) return;//剪枝
    if(dept>n)
    {
        if(sum!=res) return;
        printf("Best Pairing %d\n",++cnt);
        for(int i=1;i<=n;i++)
        {
            printf("Supervisor %d with Employee %d\n",i,num[i]);
        }
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]) continue;
        vis[i]=1;
        num[dept]=i;
        sum+=love[dept][i];
        km_dfs(dept+1);
        vis[i]=0;//回溯
        sum-=love[dept][i];//回溯
    }
}
int main()
{
    int t,x;
    scanf("%d",&t);
    for(int cas=1;cas<=t;cas++)
    {
        scanf("%d",&n);
        memset(love,0,sizeof(love));
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%d",&x);
                love[x][i]-=j;
            }
        }

        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<n;j++)
            {
                scanf("%d",&x);
                love[i][x]-=j;
            }
        }
        km();
        cnt=sum=0;
        memset(vis,0,sizeof(vis));
        //平均滿意度:因為有2*n個點,所以除以2*n
        printf("Data Set %d, Best average difference: %.6lf\n",cas,0.5*(-res)/n);
        km_dfs(1);
        printf("\n");
    }
}
最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個濱河市缘圈，隨后出現(xiàn)的幾起案子劣光，更是在濱河造成了極大的恐慌，老刑警劉巖糟把，帶你破解...
    沈念sama閱讀 217,657評論 6贊 505
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件绢涡，死亡現(xiàn)場離奇詭異，居然都是意外死亡遣疯，警方通過查閱死者的電腦和手機雄可，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,889評論 3贊 394
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來缠犀，“玉大人数苫，你說我怎么就攤上這事”嬉海” “怎么了文判？”我有些...
    開封第一講書人閱讀 164,057評論 0贊 354
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長室梅。 經(jīng)常有香客問我戏仓，道長疚宇，這世上最難降的妖魔是什么？ 我笑而不...
    開封第一講書人閱讀 58,509評論 1贊 293
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任赏殃，我火速辦了婚禮敷待，結果婚禮上，老公的妹妹穿的比我還像新娘仁热。我一直安慰自己榜揖，他們只是感情好，可當我...
    茶點故事閱讀 67,562評論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布抗蠢。 她就那樣靜靜地躺著举哟，像睡著了一般。 火紅的嫁衣襯著肌膚如雪迅矛。 梳的紋絲不亂的頭發(fā)上妨猩，一...
    開封第一講書人閱讀 51,443評論 1贊 302
  • 城市分裂傳說
    那天，我揣著相機與錄音秽褒，去河邊找鬼壶硅。 笑死，一個胖子當著我的面吹牛销斟，可吹牛的內(nèi)容都是我干的庐椒。 我是一名探鬼主播，決...
    沈念sama閱讀 40,251評論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼蚂踊，長吁一口氣：“原來是場噩夢啊……” “哼约谈！你這毒婦竟也來了？” 一聲冷哼從身側響起犁钟，我...
    開封第一講書人閱讀 39,129評論 0贊 276
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤棱诱，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后特纤，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,561評論 1贊 314
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡侥加，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,779評論 3贊 335
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年捧存，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片担败。...
    茶點故事閱讀 39,902評論 1贊 348
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡昔穴，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出提前，到底是詐尸還是另有隱情吗货，我是刑警寧澤，帶...
    沈念sama閱讀 35,621評論 5贊 345
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布狈网，位于F島的核電站宙搬，受9級特大地震影響笨腥，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜勇垛，卻給世界環(huán)境...
    茶點故事閱讀 41,220評論 3贊 328
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一脖母、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧闲孤，春花似錦谆级、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,838評論 0贊 22
  • 一樁弒父案肥照，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至勤众，卻和暖如春舆绎，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背决摧。 一陣腳步聲響...
    開封第一講書人閱讀 32,971評論 1贊 269
  • 情欲美人皮
    我被黑心中介騙來泰國打工亿蒸， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人掌桩。 一個月前我還...
    沈念sama閱讀 48,025評論 2贊 370
  • 代替公主和親
    正文 我出身青樓边锁，卻偏偏與公主長得像，于是被迫代替她去往敵國和親波岛。 傳聞我的和親對象是個殘疾皇子茅坛，可洞房花燭夜當晚...
    茶點故事閱讀 44,843評論 2贊 354

推薦閱讀更多精彩內(nèi)容

  • G - Cyclic Tour題意：圖中有n個點和m條有向邊現(xiàn)在要將該圖分成若干環(huán)，每個環(huán)中至少有兩個點则拷。環(huán)與環(huán)不...
    Gitfan閱讀 787評論 0贊 1
  • 不錯的博客求next數(shù)組: 注意:求next數(shù)組得到的最長公共前綴后綴是可以重疊的:比如:ababa,next[5...
    Gitfan閱讀 856評論 0贊 0
  • 背景 一年多以前我在知乎上答了有關LeetCode的問題, 分享了一些自己做題目的經(jīng)驗贡蓖。 張土汪：刷leetcod...
    土汪閱讀 12,744評論 0贊 33
  • （一）巴什博弈只有一堆n個物品，兩個人輪流從這堆物品中取物煌茬，規(guī)定每次至少取一個斥铺，最多取m個。最后取光者得勝坛善。顯然晾蜘，...
    Gitfan閱讀 920評論 0贊 0
  • contentSize 是scrollview可以滾動的區(qū)域，比如frame = (0 ,0 ,320 ,480)...
    chenhh6701閱讀 1,753評論 0贊 3