UESTC_The Most Wonderful Competition CDOJ 56
The Most Wonderful Competition
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Last week, School of Applied Mathematics 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.
Input
The first line of the input contains one integer T, which indicate the number of test case.
For each test case, in the first line there is an integer N (N≤16, N is always an even number) indicating there are N contestants taking part the competition.
In the next N line, 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.
Output
For each case, output the maximum total splendid level value accurate to two digits after the radix point.
Sample input and output
Sample Input | Sample Output |
---|---|
1 |
1 |
Source
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio> using namespace std;
const int maxn = + ;
double value[maxn][maxn];
double f[ << ];
bool arrive[<<];
int n;
double ans; double dfs(int cur,int val)
{
if (arrive[val])
return f[val];
arrive[val] = true;
double &ans = f[val] = -1e100;
if (val)
{
for(int i = ; i < n ; ++ i)
if (val >> i & && i != cur)
{
int next = ;
int newval = val;
newval &= ~( << i);
newval &= ~( << cur);
for(int j = ; j < n ; ++ j)
if (newval >> j & )
{
next = j;
break;
}
ans = max(ans,dfs(next,newval) + value[cur][i] );
}
}
else
ans = ;
return ans;
} int main(int argc,char *argv[])
{
int Case;
scanf("%d",&Case);
while(Case--)
{
memset(arrive,false,sizeof(arrive));
scanf("%d",&n);
for(int i = ; i < n ; ++ i)
for(int j = ; j < n ; ++ j)
scanf("%lf",&value[i][j]);
dfs(,(<<n)-);
printf("%.2lf\n",f[(<<n)-]);
}
return ;
}
最新文章
- 树形打印lua table表
- Tomcat:基于HTTP协议的Connector配置
- CommonJS/AMD/CMD/UMD概念初探
- ContentProvider官方教程(8)自定义MIME
- 搭建本地的git仓库
- 怎么给OCR文字识别软件设置正确的扫描分辨率
- android之location02
- ListView中使用type需要注意的东西
- HTML框架标签
- Project Euler 107:Minimal network 最小网络
- Apache Spark GraphX的使用简介
- HDU 5120 Intersection(几何模板题)
- C - N皇后问题(搜索)
- SVG图像技术摘要
- 使用httperrequest,模拟发送及接收Json请求
- ubuntu的常用命令
- 关于wxpython多线程研究包括(import Publisher错误研究)
- Oracle_创建用户_授予权限
- UnicodeDecodeError: &#39;utf-8&#39; codec can&#39;t decode byte 0xce in position 52: invalid continuation byte
- vue+node.js+webpack开发微信公众号功能填坑——组件按需引入