# oyjpArt ACM/ICPC算法程序设计空间

// I am new in programming, welcome to my blog
I am oyjpart(alpc12, 四城)
posts - 224, comments - 694, trackbacks - 0, articles - 6

## The perfect hamilton path

Time Limit: 5 Sec  Memory Limit: 128 MB
Submissions: 72  Solved: 16

## Description

There are N(2 <= N <= 13) cities and M bidirectional roads among the cities. There exist at most one road between any pair of the cities. Along every road, there are G pretty girls and B pretty boys(1 <= G,B <= 1000).
You want to visit every city exactly once, and you can start from any city you want to. The degree of satisfaction is the ratio of the number of the pretty girls to the number of the pretty boys. You want to know the highest degree of satisfation.

## Input

There are multiply test cases.
First line: two integers N, M;
The following M lines: every line with four integers i, j, G, B, response that there is a road between i and j with G and B.

## Output

The highest degree of the satisfation, rounded to the third place after the decimal point.

## Sample Input

`3 31 2 5 32 3 7 43 1 13 11`

`1.714`

## Source

dupeng

Solution：

#include <stdio.h>
#include
<queue>
#include
<cmath>
using namespace std;

const double EPS = 1e-4;
const int N = 15;
const int M = N * N;

#define Max(a, b) (a
>b?a:b)

inline
int dblcmp(double a, double b) {

if(fabs(a-b) < EPS) return 0;

return a < b ? -1 : 1;
}

struct Node
{

double s;
Node() {}
Node(
int mm, int xx, double ss) {
x
= xx;
= mm;
s
= ss;
}
};

int n, m;

int X[M], Y[M], G[M], B[M];

double dp[1<<N][N];

double go(double ans) {

int i, j;

for(i = 0; i < n; ++i) {
= 0;

for(j = i+1; j < n; ++j) {
}
}

for(i = 0; i < m; ++i) {
-1][Y[i]-1= G[i]-ans * B[i];
}

for(i = 0; i < (1<<n); ++i) {

for(j = 0; j < n; ++j)
dp[i][j]
= -10e100;
}
queue
<Node> Q;

for(i = 0; i < n; ++i) {
Q.push(Node(
1<<i, i, 0.0));
dp[
1<<i][i] = 0;
}

while(Q.size()) {

int f = Q.front().mask, x = Q.front().x;

double s = Q.front().s;

double& d = dp[f][x];
Q.pop();

if(s < d) continue;

for(i = 0; i < n; ++i) if((f&(1<<i)) == 0) {

if(dp[f|1<<i][i] < s + adj[x][i]) {
dp[f
Q.push(Node(f
}
}
}

double max = -10e100;

for(i = 0; i < n; ++i) {
max
= Max(max, dp[(1<<n)-1][i]);
}

return max;
}

int main()
{

// freopen("t.in", "r", stdin);

int i;

double ans;

while(scanf("%d %d"&n, &m) != EOF) {

double min = 2000, max = 0;

for(i = 0; i < m; ++i) {
scanf(
"%d %d %d %d"&X[i], &Y[i], &G[i], &B[i]);

if(B[i] < min) min = B[i];

if(G[i] > max) max = G[i];
}

double lo = 0, hi = max/min;

int ok = 0;

for(i = 0; ; ++i) {

double mid = lo + (hi-lo)/2;

if(dblcmp((ans=go(mid)), 0.0> 0) {
lo
= mid;
}
else if(dblcmp(ans, 0.0== 0) {
printf(
"%.3lf\n", mid);
ok
= 1;

break;
}
else {
hi
= mid;
}
}

if(!ok) { int a = 0; a = 1/a; }
}

return 0;
}

### Feedback

3.地震--最有比率生成树 一节的解答

go函数实际求的就是最大权的hamilton回路。用的是基本的压缩状态广搜。

#include <stdio.h>

#define N 13

{
int nBoys;
int nGirls;
double dRatio;

int g_Path[2][N];
int g_PathIndex[2] = {0};
double g_dRatio[2] = {0.0};

int FindNextNode(int nPathIndex, int nLine)
{
double dRatio = 0;
int nNode = 0;
int i = 0;
int j = 0;
bool bExist = false;

for (j = 0; j < nCities; j++)
{
for (i = 0; i < g_PathIndex[nPathIndex]; i++)
{
if (j == g_Path[nPathIndex][i])
{
bExist = true;
break;
}
}
if (bExist)
{
bExist = false;
continue;
}
{
nNode = j;
}
}

return nNode;
}

int FindPath(int nPathIndex, int nNode)
{
int nNextNode = 0;
static int nBoys = 0, nGirls = 0;

g_Path[nPathIndex][g_PathIndex[nPathIndex]] = nNode;
g_PathIndex[nPathIndex]++;
if (g_PathIndex[nPathIndex] >= nCities)
{
g_dRatio[nPathIndex] = (double)nGirls / nBoys;
return 0;
}

nNextNode = FindNextNode(nPathIndex, nNode);
FindPath(nPathIndex, nNextNode);

return 0;
}

int main()
{
int i,j,nGirls,nBoys;
char q = '0';
int nPathIndex = 0;

i = j = nGirls = nBoys = 0;

printf("Input the number of cities and roads:\n");

if (nCities < 1 || nRoads < 1)
{
return 1;
}

do
{
printf("Input the road index and the number of girls and boys sequentially : "
"from to girls boys\n");
scanf("%d %d %d %d", &i, &j, &nGirls, &nBoys);
getchar();

g_AdjNode[i - 1][j - 1].nBoys = nBoys;
g_AdjNode[i - 1][j - 1].nGirls = nGirls;
g_AdjNode[i - 1][j - 1].dRatio = (double)nGirls / nBoys;
g_AdjNode[j - 1][i - 1].nBoys = nBoys;
g_AdjNode[j - 1][i - 1].nGirls = nGirls;

printf("Input finished?(y/n)");
scanf("%c", &q);
getchar();
} while ('y' != q);

//process here
nPathIndex = 0;
for (i = 0; i < nCities; i++)
{
FindPath(nPathIndex, 0);
nPathIndex = g_dRatio[0] <= g_dRatio[1] ? 0 : 1;
g_PathIndex[nPathIndex] = 0;
}

//output the result
nPathIndex = g_dRatio[0] >= g_dRatio[1] ? 0 : 1;
printf("The max ratio is %.3lf\n", g_dRatio[nPathIndex]);\
printf("The best path : \n");
for (i = 0; i < nCities; i++)
{
printf("%d\t", g_Path[nPathIndex][i]);
}
printf("\n");

return 0;
}

if (g_PathIndex[nPathIndex] >= nCities)
{
g_dRatio[nPathIndex] = (double)nGirls / nBoys;
nGirls = nBoys = 0;
return 0;
}
@Surfing

@richardxx

@ 小Young

 只有注册用户登录后才能发表评论。 相关文章: