Posted on 2008-06-03 15:45
oyjpart 閱讀(3130)
評論(14) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
上次百度之星第三題竟然不會做，很是慚愧啊，腦袋生銹了。
后來從HUST上面找了道類似的題目，AC了。
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 3
1 2 5 3
2 3 7 4
3 1 13 11
Sample Output
1.714
HINT
Source
dupeng
題目的意思是找到一個sigma(G)/sigma(B)最大的hamilton回路。
典型的參數搜索。二分或者迭代答案就可以了。
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
{
int x, mask;
double s;
Node() {}
Node(int mm, int xx, double ss) {
x = xx;
mask = mm;
s = ss;
}
};
int n, m;
double adj[N][N];
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) {
adj[i][i] = 0;
for(j = i+1; j < n; ++j) {
adj[i][j] = adj[j][i] = -10e300;
}
}
for(i = 0; i < m; ++i) {
adj[X[i]-1][Y[i]-1] = G[i]-ans * B[i];
adj[Y[i]-1][X[i]-1] = adj[X[i]-1][Y[i]-1];
}
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|1<<i][i] = s + adj[x][i];
Q.push(Node(f|1<<i, i, s + adj[x][i]));
}
}
}
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;
}