主题:[讨论]这个用什么算法哦?
Description 问题描述
Last week, School held a competition of flying kite, contestants are divided into pairs, and one contestant competes with another in each pair. As we know, different way dividing pairs may bring different splendid level value, which appears as a real numbers. Now Miss Ye wants to know how to divide the competitor in order to attain maximum splendid level.
there are N contestants taking part the competition.(N为偶数)
there are N lines, each line contains N real numbers. The j-th number in the i-th line is the splendid level value when the i-th contestant and the j-th constant are made in one pair. You can assume the j-th number in the i-th line is equal to the i-th number in the j-th line.
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0
output the maximum total splendid level value
这个用什么算法好呀?求指点
我的程序哪里有错哦?
#include<stdio.h>
#include<stdlib.h>
int main()
{
int T;
scanf("%d",&T);//读入有多少测试数据
while(T--)
{
int N,i,j;
scanf("%d",&N);
float won[N][N],value=0.0,max;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%f",&won[i][j]);//读入数据
//处理数据
int k=0;
while(k!=(N/2))
{
k++;
int S,T;
max=-0.1;
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
{
if(max<won[i][j])
if(won[i][j]!=-0.1)
{ max=won[i][j];
S=i;
T=j;
}
}
value=value+max;
for(i=0;i<N;i++)
{
won[S][i]=-0.1;
won[T][i]=-0.1;
won[i][S]=-0.1;
won[i][T]=-0.1;
}
}
printf("%.2f\n",value);
}
return 0;
}
Last week, School held a competition of flying kite, contestants are divided into pairs, and one contestant competes with another in each pair. As we know, different way dividing pairs may bring different splendid level value, which appears as a real numbers. Now Miss Ye wants to know how to divide the competitor in order to attain maximum splendid level.
there are N contestants taking part the competition.(N为偶数)
there are N lines, each line contains N real numbers. The j-th number in the i-th line is the splendid level value when the i-th contestant and the j-th constant are made in one pair. You can assume the j-th number in the i-th line is equal to the i-th number in the j-th line.
0 1 2 3
1 0 4 5
2 4 0 6
3 5 6 0
output the maximum total splendid level value
这个用什么算法好呀?求指点
我的程序哪里有错哦?
#include<stdio.h>
#include<stdlib.h>
int main()
{
int T;
scanf("%d",&T);//读入有多少测试数据
while(T--)
{
int N,i,j;
scanf("%d",&N);
float won[N][N],value=0.0,max;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
scanf("%f",&won[i][j]);//读入数据
//处理数据
int k=0;
while(k!=(N/2))
{
k++;
int S,T;
max=-0.1;
for(i=0;i<N;i++)
for(j=i+1;j<N;j++)
{
if(max<won[i][j])
if(won[i][j]!=-0.1)
{ max=won[i][j];
S=i;
T=j;
}
}
value=value+max;
for(i=0;i<N;i++)
{
won[S][i]=-0.1;
won[T][i]=-0.1;
won[i][S]=-0.1;
won[i][T]=-0.1;
}
}
printf("%.2f\n",value);
}
return 0;
}