P1559 运动员最佳匹配问题

输入输出格式

输入格式:

率先尽有1 个正整数n
(1≤n≤20)。接下来的2n行,每行n个数。前n行是p,后n行是q。

出口格式:

拿计产生之男女双方竞赛优势的总额的绝酷价值输出。

叹气向都是最后之地下。—题记

输入输出样例

输入样例#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;
}

 

 

1

日本奈良的清晨,小林俊介又打习的睡梦中惊醒,梦里是海滨市的暮色,海市蜃楼的景物撩人。那种给皮筋勒住手指的觉得还在稳稳地镇住他的神经,使他平静—像奈良的清晨。小林俊介不觉得清晨时有发生差不多安宁,光线刺眼,风吹过都如在侵犯。

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

题材叙述

羽毛球队有男性阴运动员各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]。设计一个算法,计算男女选手最佳配对法,使各组男女双方竞赛优势的总和达到最可怜。

2

初中生小林俊介很靠近本分,因为从小家教严格。学校是均等所均封闭式的过夜学校,小林俊介身材瘦削,时常成为欺凌的目标。班上发出了号称捣蛋的“橙色兄弟”总好拿他取乐,最沉痛的等同不好是自丢半独耳垂。即使挨了于,“橙色兄弟”受到教导处警告,小林俊介的心房已蒙下了怕与不安的米,这让他想到了平时以女人吃的辱骂。父母不在家也未曾关心他的烦恼,自卑得找不顶朋友,那些日子,小林俊介总是梦见自己吃缚,折磨,醒矣便趁早在夜间大家睡着的早晚溜出去看清冷的月光。小林俊介孤影相伴,就于平安夜前夕,同学等吵吵嚷嚷三还半夜间才完全睡去,节日之隆重让小林俊介尤为郁结,月色下的教室一片狼藉。打闹后底瓦砾:礼花,喷雾剂,散落的礼物盒,纸袋还有少的行装,桌子椅子横七竖八,

黑板上被挫折了一样万分团食用黄油,粘着一个妇人领结,阴性的,不定式的。小林俊介看在教室,突然地,窗户外一样仅小鸟的身影一闪,是夜莺吗?小林俊介记得4年度时以爱妻的地窖找到同样如约旧旧的【安徒生童话】,说夜莺是会歌唱的飞禽,可以带来福灵。眼前的鸟类低飞在,然后抱于课桌上,倒了下,这是平只有受伤的禽,右腿有伤痕。小林俊介绞了平等段子纱布把受伤的地方钻好,找来一个盒子,一边想象夜莺唱歌一边将其藏起来。绝不会落入他手。在拿管扎好伤口的禽放入盒子的同一寺院那,月光下那只鸟的视力,神圣清净,旁边摆在蜡烛,像是受平安夜送及之首先首赞歌。

小林俊介有一段时间没做梦了,每天看在鸟儿康复使他平静,甚至快,连“橙色兄弟”也无克影响至他。这仅小鸟成了他的隐秘,一把钥匙,给了外答案。他觉得有雷同栽鸟类羽毛特别油亮,是关不停止的,而就虽是那无非上帝之夜莺。一个晚小林俊介睡得特别不安,这很怪。他翻身起床,径直走至那鸟的潜伏之所。走至一半,月光依然,淅淅沥沥拍起在窗户上,远远地扩散不调和的嬉闹声,是“橙色兄弟”,几只玩世不恭的男孩子不知从哪行来蜡烛,像电视里那么围成一个环点燃,那只是夜莺就在中等。夜莺!小林俊介踢碎窗户玻璃冲过去,冲在他们同样拳脚,“橙色兄弟”见老大被起一窝蜂把他以到,蜡烛灭了大体上,剩余的烛光中,那只是夜莺惨不忍睹,小林俊介的血印混杂在冰雪一般的羽绒,粘在贴在本土的脸孔,他受于伤了,夜莺死了,暗淡无光。小林俊介的痛涌了上来,他挣脱箍住的一手,朝着小腹一阵猛踹,倒了一个,另一个而且来接招。小林俊介一直当起,不顾死活,后来复为尚无来学。

3

下班晚底小林俊介没有当今日发生什么不同,走及地铁,一个牵动在鸭舌帽看无到底脸面的男子汉为在外身边,突然伸出拿空玻璃啤酒瓶的手来其奇怪的来了一晃…

小林俊介站在明晃晃日光下,之前有了呀一无所知,也未知底怎么就到了这里,这间教室。崭新一切开,没有人。小林俊介呆呆的,这就是坏曾今给他带过平静,抚慰了他的声呢?窗外阳光滚滚,小林俊介很欢喜,那只夜莺变成了太阳鸟,羽毛如烟花,它再次,生了,小林俊介觉得温的,昏昏得沉睡了…

地铁上之小林俊介睁开眼睛,错过好几站了,身边的绝密男子在读报,似笑不笑地看了他相同双眼,到站下车了。小林俊介惊叹此人的奇异,他是干净傻了,一秒前还记得吃人袭击,然后又梦到自己跟重生的夜莺,但是,他确实清醒了。

如出一辙年后小林俊介离开了奈良去矣一致所海滨城市,走前面拜访了年已双稀的老人,家具意见呢远非带。在新的城,小林俊介按照自己之方法在在,收留流浪的动物,施舍乞丐,并且与组成部分总人口做了情人,小林俊介知道,只有团结放弃了几趟自己之物,他才能够无所畏惧,只有征服和摸索,他的日子才能够延续。他无见面重复夺做一些失败品的傀儡,给协调的自卑加相同码外衣,更非会见畏首畏尾了。小林俊介自发生异的上帝,上帝都为他派遣过去同等但夜莺。

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