青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

oyjpArt ACM/ICPC算法程序設計空間

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

基本參數搜索

Posted on 2008-06-03 15:45 oyjpart 閱讀(3140) 評論(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;
}

 


Feedback

# re: 基本參數搜索  回復  更多評論   

2008-06-04 13:43 by w
你好,這個程序我看不懂……能講一下思路嗎?

# re: 基本參數搜索  回復  更多評論   

2008-06-04 14:56 by oyjpart
你可以參考《算法藝術與信息學競賽》303-304頁
3.地震--最有比率生成樹 一節的解答
和這個非常類似

就是2分枚舉那個答案,然后將除的表達式的權 轉化成+-*表達式的權,再這個基礎上求目標函數。 如果目標函數 != 0,則枚舉的答案應該向使目標函數更接近0的方向取值,

go函數實際求的就是最大權的hamilton回路。用的是基本的壓縮狀態廣搜。

# re: 基本參數搜索  回復  更多評論   

2008-06-04 15:02 by Surfing
我的解法

#include <stdio.h>

#define N 13

typedef struct _T_AdjNode
{
int nBoys;
int nGirls;
double dRatio;
}TAdjNode;

TAdjNode g_AdjNode[N][N];
int g_Path[2][N];
int g_PathIndex[2] = {0};
double g_dRatio[2] = {0.0};
int nCities, nRoads;

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;
}
if (g_AdjNode[nLine][j].dRatio > dRatio)
{
dRatio = g_AdjNode[nLine][j].dRatio;
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);
nBoys += g_AdjNode[nNode][nNextNode].nBoys;
nGirls += g_AdjNode[nNode][nNextNode].nGirls;
FindPath(nPathIndex, nNextNode);

return 0;
}

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

nCities = nRoads = 0;
i = j = nGirls = nBoys = 0;

printf("Input the number of cities and roads:\n");
scanf("%d %d", &nCities, &nRoads);

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;
g_AdjNode[j - 1][i - 1].dRatio = g_AdjNode[i - 1][j - 1].dRatio;

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;
}

# re: 基本參數搜索  回復  更多評論   

2008-06-04 15:10 by Surfing
一點小問題,更正一下

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

# re: 基本參數搜索  回復  更多評論   

2008-06-04 17:13 by oyjpart
@Surfing
嘿嘿,謝謝分享

# re: 基本參數搜索  回復  更多評論   

2008-06-05 22:27 by w
多謝,受教了

# re: 基本參數搜索  回復  更多評論   

2008-06-05 23:07 by oyjpart
不謝

# re: 基本參數搜索  回復  更多評論   

2008-06-09 23:54 by richardxx
我做了百度那題,但比賽完才想起我貼的那個模版有點問題,最后果然只有4.5分,和沒做沒區別~~

# re: 基本參數搜索  回復  更多評論   

2008-06-10 12:03 by oyjpart
@richardxx
呵呵 進復賽了就可以了不 看我們這種初賽就被水掉的菜菜。。

# re: 基本參數搜索  回復  更多評論   

2008-06-10 20:01 by 小Young
跟著大牛漲經驗值!

# re: 基本參數搜索  回復  更多評論   

2008-06-10 20:34 by oyjpart
汗。。。
您謙虛了。。。

# re: 基本參數搜索  回復  更多評論   

2008-06-11 19:12 by 小Young
請問這題你用隊列有什么用途啊?
這題不用隊列也可以啊.

# re: 基本參數搜索  回復  更多評論   

2008-06-11 22:19 by oyjpart
@ 小Young
就是廣搜用的隊列
不用隊列你的意思是深搜么?

# re: 基本參數搜索  回復  更多評論   

2008-07-26 06:09 by lengbufang
看看!!!
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            久久九九久久九九| 欧美中文字幕| 91久久精品国产| 欧美国产日韩视频| 亚洲免费观看在线观看| 亚洲日韩视频| 欧美婷婷六月丁香综合色| 亚洲欧美在线高清| 亚洲欧美激情诱惑| 精品成人在线视频| 亚洲三级免费电影| 国产精品天天看| 欧美xx69| 国产精品久久久久久久久久久久久 | 99国产精品私拍| 国产精品国产三级欧美二区| 欧美一区二区三区四区视频| 久久久国产精品亚洲一区| 亚洲人午夜精品| 亚洲一区免费看| 亚洲美女电影在线| 国产一区二区三区精品久久久 | 极品少妇一区二区三区精品视频| 欧美成人69av| 欧美性色aⅴ视频一区日韩精品| 久久av在线| 欧美精品一区在线发布| 欧美在线免费观看亚洲| 欧美成人精品在线播放| 午夜精品视频网站| 欧美激情国产日韩精品一区18| 午夜久久福利| 欧美区一区二区三区| 久久久久国产精品午夜一区| 欧美精品在线免费播放| 久久亚洲图片| 国产美女扒开尿口久久久| 亚洲激情一区二区三区| 国产一区二区按摩在线观看| 99综合视频| 亚洲欧洲免费视频| 欧美一区二区久久久| 亚洲一卡久久| 欧美另类女人| 亚洲高清资源| 亚洲第一二三四五区| 亚洲一区二区av电影| aa成人免费视频| 老司机成人网| 麻豆精品在线视频| 国产亚洲欧美一区| 亚洲欧美日韩综合| 亚洲免费在线观看视频| 欧美日本韩国| 亚洲精品日韩欧美| 99视频一区二区三区| 欧美国产丝袜视频| 亚洲第一综合天堂另类专| 黄色成人片子| 久久久九九九九| 麻豆精品91| 激情丁香综合| 久久综合九色综合欧美就去吻| 久久香蕉国产线看观看网| 国产欧美一区二区视频| 亚洲欧美资源在线| 久久精品二区| 黄色亚洲网站| 久久影院亚洲| 亚洲黄色尤物视频| 一区二区三区回区在观看免费视频| 免费亚洲一区二区| 亚洲裸体在线观看| 亚洲私人影院| 国产情人节一区| 久久激情五月激情| 欧美激情麻豆| 一区二区三区你懂的| 欧美手机在线| 性欧美大战久久久久久久免费观看| 欧美一区二区三区视频在线| 国内精品视频在线播放| 另类图片综合电影| 亚洲久久一区| 欧美伊人久久久久久午夜久久久久 | 亚洲一区在线免费观看| 欧美成人精品一区| 亚洲美女在线观看| 亚洲欧美日韩精品综合在线观看| 国产农村妇女毛片精品久久麻豆| 欧美一区二区三区免费大片| 欧美成人在线网站| 亚洲一区二区免费视频| 国产在线高清精品| 欧美精品久久一区二区| 亚洲午夜电影在线观看| 看片网站欧美日韩| 亚洲视频一区二区在线观看| 国产日韩欧美| 欧美精品久久久久a| 欧美一区午夜精品| 亚洲精品五月天| 久久综合九色九九| 亚洲欧美高清| 亚洲精品裸体| 国产真实精品久久二三区| 欧美成人精品不卡视频在线观看| 一区二区三区黄色| 亚洲电影免费| 久久精品一区二区三区不卡| 一片黄亚洲嫩模| 在线欧美日韩国产| 国产欧美日韩亚洲精品| 欧美激情精品久久久六区热门| 亚洲欧美日韩中文播放| 亚洲伦理在线| 亚洲第一天堂无码专区| 久久精品国产综合精品| 中文av一区二区| 91久久综合| 尤物在线精品| 国内自拍亚洲| 国产精品一区二区久久国产| 欧美人交a欧美精品| 久久夜色精品国产欧美乱极品| 亚洲一区二区三区久久| 日韩一级视频免费观看在线| 欧美激情亚洲视频| 免费短视频成人日韩| 久久精品中文| 久久国产加勒比精品无码| 亚洲免费人成在线视频观看| 亚洲日本中文字幕免费在线不卡| 国内精品国语自产拍在线观看| 国产精品香蕉在线观看| 欧美日韩亚洲一区二区三区四区| 欧美超级免费视 在线| 久久综合国产精品| 玖玖综合伊人| 欧美成人精品1314www| 欧美成人伊人久久综合网| 久久综合久久美利坚合众国| 久久这里只有精品视频首页| 久久一区二区三区av| 久久亚洲精品一区| 美女国产一区| 欧美精品自拍| 欧美性做爰猛烈叫床潮| 国产精品理论片在线观看| 国产精品久久久爽爽爽麻豆色哟哟| 国产精品国产三级国产aⅴ浪潮| 欧美日韩在线不卡一区| 欧美视频精品在线观看| 国产精品久久久久秋霞鲁丝| 国产精品一区二区三区四区| 国产精品久久夜| 国产日产亚洲精品系列| 狠狠综合久久av一区二区小说 | 一区二区三区回区在观看免费视频| 日韩午夜激情av| 亚洲一区欧美激情| 久久久噜噜噜久久| 欧美刺激性大交免费视频| 亚洲电影免费观看高清完整版在线| 国产一区二区三区黄视频| 亚洲大片免费看| 99国产精品视频免费观看| 亚洲欧美中文日韩v在线观看| 欧美中日韩免费视频| 欧美 亚欧 日韩视频在线| 亚洲精品乱码久久久久久蜜桃麻豆 | 亚洲国产成人av在线| 99国产精品自拍| 久久福利视频导航| 亚洲高清自拍| 亚洲一二区在线| 美脚丝袜一区二区三区在线观看 | 亚洲精品欧美激情| 午夜欧美精品久久久久久久| 久久综合伊人77777麻豆| 亚洲精品免费一区二区三区| 亚洲与欧洲av电影| 欧美电影打屁股sp| 国产欧美日韩亚洲| 一本色道久久精品| 开元免费观看欧美电视剧网站| 日韩亚洲欧美高清| 久久久久久久精| 国产精品区免费视频| 亚洲国产日本| 久久久久亚洲综合| 亚洲精品在线观| 久久综合九色综合欧美狠狠| 国产精品一国产精品k频道56| 91久久精品国产| 久久久久国产精品人| 亚洲视频在线观看| 欧美精品午夜| 最新国产成人在线观看| 久久亚洲精品一区二区|