P1559 运动员最佳匹配问题

 洛谷——P1559 运动员最佳匹配问题

叹气向还是最终之机密。—题记

问题叙述

羽毛球队有男性阴运动员各n人。给得2
单n×n矩阵P和Q。P[i][j]大凡男运动员i和女性运动员j配对做混合双打的男运动员竞赛优势;Q[i][j]凡女运动员i和男性选手j配合的女性运动员比试优势。由于技术相当和心理状态等各种因素影响,P[i][j]免自然当Q[j][i]。男运动员i和女运动员j配对成混合双打的男女双方竞赛优势为P[i][j]*Q[j][i]。设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最好特别。

1

日本奈良的清早,小林俊介又打习的梦中惊醒,梦里是海滨都会之夜色,海市蜃楼的风物撩人。那种让皮筋勒住手指的感到还以稳稳地镇住他的神经,使他稳定—像奈良的清晨。小林俊介不觉得清晨出差不多安宁,光线刺眼,风吹过都像以侵犯。

早饭吃得好少,小林俊介没有食欲,窗外白鸽的翅膀震耳欲聋,在外看来只是单调的振幅。上班的地铁达到因为满了沙丁鱼一般的人流,三分之一背着在双肩背包,三分之一穿过白色尼龙袜子。还有的三分之一遗弃在人群里就是重新为觅不交了。大家沉默地连排除为,不吵闹,脸上不悲不喜。小林俊介这时候最放松,他热爱这种严寒的觉得,他就是比如相同块纯棉的白布,被尖的刀口绞着剪着,这种冷,尤其要他振奋。工作之中的单人隔间紧紧连却互不相干,大家志愿地维持这同一栽秩序—可能并死呢是。小林俊介没想过怪,没想了音乐,女人更是深恶痛绝,她们捉摸不定,疑神疑鬼,自卑多情。小林俊介的平等龙过去了。

输入输出格式

输入格式:

第一实施有1 个正整数n
(1≤n≤20)。接下来的2n行,每行n个数。前n行是p,后n行是q。

出口格式:

拿计产生的男女双方竞赛优势的总数的极度老价值输出。

2

初中生小林俊介很近本分,因为从小家教严格。学校是一致所均封闭式的下榻学校,小林俊介身材瘦削,时常成为欺凌的靶子。班上闹了名捣蛋的“橙色兄弟”总好拿他取乐,最重的如出一辙不善是于丢半个耳垂。即使挨了起,“橙色兄弟”受到教导处警告,小林俊介的方寸已经覆盖下了害怕和不安的子,这叫他想到了平时在太太吃的辱骂。父母未在家吗并未关心他的闷,自卑得找不交朋友,那些日子,小林俊介总是梦见自己被捆,折磨,醒矣就是趁机在夜间大家睡着的当儿溜出去看清冷的月光。小林俊介孤影相伴,就在平安夜前夕,同学等吵吵嚷嚷三还半夜才完全睡去,节日的红火让小林俊介尤为郁结,月色下之教室一片狼藉。打闹后的废墟:礼花,喷雾剂,散落的礼物盒,纸袋还有少的行装,桌子椅子横七竖八,

黑板上让砸了平等十分团食用黄油,粘在一个妇人领结,阴性的,不定式的。小林俊介看在教室,突然地,窗户外一样但小鸟的人影一闪,是夜莺吗?小林俊介记得4年份经常于老伴的地窖找到同样按部就班旧旧的【安徒生童话】,说夜莺是会见歌唱的鸟类,可以带动福灵。眼前之鸟儿低飞在,然后拿走于课桌上,倒了下去,这是千篇一律只有受伤的鸟,右腿有伤痕。小林俊介绞了平截纱布把受伤的地方钻好,找来一个盒子,一边想象夜莺唱歌一边把它藏起来。绝不会落入他手。在管保险扎好伤口的鸟类放入盒子的一致寺那,月光下那只鸟的眼神,神圣清净,旁边摆在蜡烛,像是受平安夜送及的第一首赞歌。

小林俊介有一段时间没做梦了,每天看正在鸟儿康复使他坦然,甚至快,连“橙色兄弟”也不能够影响到他。这仅小鸟成了外的地下,一管钥匙,给了外答案。他道出同种鸟类羽毛特别油亮,是关不歇的,而立即就算是那就上帝之夜莺。一个夜晚小林俊介睡得特别不安,这可怜尴尬。他翻身起来,径直走至那鸟的藏身的所。走及一半,月光依然,淅淅沥沥拍起在窗户上,远远地传出不协调的嬉闹声,是“橙色兄弟”,几独玩世不恭的男孩子不知从哪来来蜡烛,像电视里那样围成一个圈点燃,那无非夜莺就当中等。夜莺!小林俊介踢碎窗户玻璃冲过去,冲着她们一致拳脚,“橙色兄弟”见老大被起一窝蜂把他本到,蜡烛灭了大体上,剩余的烛光中,那只夜莺惨不忍睹,小林俊介的血迹混杂在冰雪一般的毛,粘在贴在该地的脸庞,他给于伤了,夜莺死了,暗淡无光。小林俊介的悲愤涌了上,他挣脱箍住的手段,朝着小腹一阵猛踹,倒了一个,另一个而来接招。小林俊介一直在起,不顾死活,后来复为没来校。

3

下班后的小林俊介没有看今日时有发生啊不同,走及地铁,一个带动在鸭舌帽看无到头脸面的男子汉为在他身边,突然伸出拿空玻璃啤酒瓶的手来那竟的来了瞬间…

小林俊介站在明晃晃日光下,之前发生了啊一无所知,也非理解怎么就赶到了此地,这个中教室。崭新一切片,没有丁。小林俊介呆呆的,这虽是甚曾今给他带动过平静,抚慰了他的声也?窗外阳光滚滚,小林俊介很欣喜,那不过夜莺变成了太阳鸟,羽毛如烟花,它再,生了,小林俊介觉得温暖的,昏昏得沉睡了…

地铁直达之小林俊介睁开眼睛,错过好几站了,身边的神秘男子以读报,似笑不笑地扣押了外同样双眼,到站下车了。小林俊介惊叹此人的怪,他是穷傻了,一秒前还记给人袭击,然后还要梦到好和重生的夜莺,但是,他真清醒了。

无异于年后小林俊介离开了奈良去矣一如既往座海滨城市,走前面拜访了年都双稀的养父母,家具意见呢从不带。在新的都市,小林俊介按照自己之方生存着,收留流浪的动物,施舍乞丐,并且与局部口做了爱人,小林俊介知道,只有和谐放弃了几次自己的事物,他才会无所畏惧,只有征服和查找,他的生活才能够连续。他非见面另行去做一些失败品的傀儡,给协调的自卑加同码外衣,更无见面畏首畏尾了。小林俊介自出客的上帝,上帝都受他派遣过去同样仅仅夜莺。

输入输出样例

输入样例#1:

3
10 2 3
2 3 4
3 4 5
2 2 2
3 5 3
4 5 1
输出样例#1:

52

思路


代码:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 40
#define maxn 9999999
using namespace std;
int n,a[N][N],b[N][N],love[N][N];
bool vis_boy[N],vis_girl[N];
int pre[N],remain[N],ex_girl[N],ex_boy[N];
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int dfs(int girl)
{
    vis_girl[girl]=true;
    for(int i=1;i<=n;i++)
    {
        if(vis_boy[i]) continue;
        int ex=ex_boy[i]+ex_girl[girl]-love[girl][i];
        if(ex==0) 
        {
            vis_boy[i]=true;
            if(pre[i]==-1||dfs(pre[i]))
            {pre[i]=girl; return 1;}
        }
        else remain[i]=min(remain[i],ex);
    }
    return false;
}
int km()
{
    memset(ex_boy,0,sizeof(ex_boy));
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      ex_girl[i]=max(ex_girl[i],love[i][j]);
    for(int i=1;i<=n;i++)
    {
        memset(remain,0x7fff,sizeof(remain));
        while(1)
        {
            memset(vis_boy,0,sizeof(vis_boy));
            memset(vis_girl,0,sizeof(vis_girl));
            if(dfs(i)) break;
            int d=maxn;
            for(int i=1;i<=n;i++)
             if(!vis_boy[i]) d=min(d,remain[i]);
            for(int i=1;i<=n;i++)
            {
                if(vis_boy[i]) ex_girl[i]-=d;
                if(vis_girl[i]) ex_boy[i]+=d;
                else remain[i]-=d;
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
     ans+=love[pre[i]][i];
    return ans;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      a[i][j]=read();
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      b[i][j]=read();
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      love[i][j]=a[i][j]*b[j][i];
   printf("%d\n",km());
   return 0;
 } 

 

#include<cstdio>
#include<iostream>
#define MAXN 110
#define INF 1000000000
using namespace std;
int lx[MAXN],ly[MAXN];
int f[MAXN][MAXN],n,m,pre[MAXN],pre2[MAXN];
bool vx[MAXN],vy[MAXN];
inline void read(int&x) {
    int f=1;x=0;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=10*x+c-48,c=getchar();
    x=x*f;
}
inline void pra() {
    for(int i=1;i<=n;i++) 
      for(int j=1;j<=m;j++)
        lx[i]=max(lx[i],f[i][j]);
}
inline bool find(int u) {
    vx[u]=true;
    for(int i=1;i<=m;i++) {
        if(lx[u]+ly[i]==f[u][i]&&!vy[i]) {
            vy[i]=true;
            if(!pre[i]||find(pre[i])) {
                pre[i]=u;
                pre2[u]=i;
                return true;
            }
        }
    }
    return false;
}
inline void renew() {
    int t=INF;
    for(int i=1;i<=n;i++)
      if(vx[i])
        for(int j=1;j<=m;j++)
          if(!vy[j])
            t=min(t,lx[i]+ly[j]-f[i][j]);
    for(int i=1;i<=n;i++)
      if(vx[i]) lx[i]-=t;
    for(int j=1;j<=m;j++)
      if(vy[j]) ly[j]+=t;
}
inline void km() {
    for(int i=1;i<=n;i++) 
    while(true){
        for(int j=1;j<=n;j++) vx[j]=false;
        for(int j=1;j<=m;j++) vy[j]=false;
        if(find(i)) break;
        else renew();
    }
}
int main() {
    read(n);read(m);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        read(f[i][j]);
    pra();
    km();
    int ans=0;
    for(int i=1;i<=n;i++)
      ans+=f[i][pre2[i]];
    printf("%d\n",ans);
    return 0;
}