| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 559 人关注过本帖
标题:最佳组队问题求错
只看楼主 加入收藏
huang__mz
Rank: 2
等 级:论坛游民
帖 子:9
专家分:26
注 册:2010-8-28
结帖率:50%
收藏
已结贴  问题点数:20 回复次数:4 
最佳组队问题求错
双人混合ACM程序设计竞赛即将开始,因为是双人混合赛,故每支队伍必须由1男1女组成。现在需要对n名男队员和n名女队员进行配对。由于不同队员之间的配合优势不一样,因此,如何组队成了大问题。
给定n×n优势矩阵P,其中P[i][j]表示男队员i和女队员j进行组队的竞赛优势(0<P[i][j]<10000)。设计一个算法,计算男女队员最佳配对法,使组合出的n支队伍的竞赛优势的总和达到最大值
第一行输入n表示有n×n个人
接着输入n行数据
输出最大的优势值
我的思路是先从行列置1的数中挑出一个最大的值,把他的行列置1,然后继续挑最大的数
我的代码是

#include <stdio.h>
int main()
{
     int p[10][10],k[10];
     int a,n,i,j,jj,x,flag1[10],flag2[10],ii,b;
     while(scanf("%d",&n)!=EOF&&n>=1)
     {
     x=0;
     for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
             scanf("%d",&p[i][j]);
     for(j=1;j<=n;j++)
         flag1[j]=flag2[j]=0;
     for(i=1;i<=n;i++)
     {
         k[i]=0;
         for(ii=1;ii<=n;ii++)
         {
             if(flag2[ii]==0)
             {
                 for(jj=1;jj<=n;jj++)
                 {
                       if(flag1[jj]==0 )
                       {
                           if(p[ii][jj]>k[i])
                           {
                             k[i]=p[ii][jj];
                             a=jj;
                           b=ii;
                           }
                       }
                 }
             }   
         }
         flag1[a]=1;
             flag2[b]=1;
     }
     for(i=1;i<=n;i++)
        x=x+k[i];
     printf("%d\n",x);
     }
     return 0;
}
测试数组
3
10 2 3
2 3 4
3 4 5
输出18
搜索更多相关主题的帖子: 组队 
2010-09-03 09:39
liqinm
Rank: 2
等 级:论坛游民
帖 子:13
专家分:39
注 册:2010-8-31
收藏
得分:6 
KM?

my name is liqin
2010-09-03 10:39
encounter
Rank: 5Rank: 5
来 自:扬州
等 级:职业侠客
威 望:2
帖 子:150
专家分:359
注 册:2010-7-24
收藏
得分:6 
每行,每列都只能选一个

简单写下
先找最大   将下标[i][j]记下   b[m][2]  m++   
再找次大
for(     )
if(i!=b[][0]&&j!=b[][1])
将下标记录到b[][2]    go on  到n即可
最后将p[b[][0]][b[][1]]求和




ping   nbtstat   netstat   tracert    nat   at    ftp   telnet..................
2010-09-03 12:56
huang__mz
Rank: 2
等 级:论坛游民
帖 子:9
专家分:26
注 册:2010-8-28
收藏
得分:0 
找最大是错的,提交上去一直都是wrong answer 要是遇到两个一样的数就错了如10 10 3\10 2 3\2 2 4
2010-09-03 14:03
快速回复:最佳组队问题求错
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.018144 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved