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

oyjpArt ACM/ICPC算法程序設(shè)計(jì)空間

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

基本參數(shù)搜索

Posted on 2008-06-03 15:45 oyjpart 閱讀(3140) 評(píng)論(14)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

上次百度之星第三題竟然不會(huì)做,很是慚愧啊,腦袋生銹了。

后來從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


題目的意思是找到一個(gè)sigma(G)/sigma(B)最大的hamilton回路。
典型的參數(shù)搜索。二分或者迭代答案就可以了。

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: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

就是2分枚舉那個(gè)答案,然后將除的表達(dá)式的權(quán) 轉(zhuǎn)化成+-*表達(dá)式的權(quán),再這個(gè)基礎(chǔ)上求目標(biāo)函數(shù)。 如果目標(biāo)函數(shù) != 0,則枚舉的答案應(yīng)該向使目標(biāo)函數(shù)更接近0的方向取值,

go函數(shù)實(shí)際求的就是最大權(quán)的hamilton回路。用的是基本的壓縮狀態(tài)廣搜。

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

2008-06-04 15:10 by Surfing
一點(diǎn)小問題,更正一下

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

2008-06-10 20:01 by 小Young
跟著大牛漲經(jīng)驗(yàn)值!

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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

# re: 基本參數(shù)搜索  回復(fù)  更多評(píng)論   

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>
            亚洲激情一区| 欧美激情亚洲| 亚洲精品久久久蜜桃| 欧美精品国产| 亚洲欧美日韩在线观看a三区| 日韩一本二本av| 欧美性猛交99久久久久99按摩 | 欧美人与禽猛交乱配| 一区二区三区四区五区在线| 中文欧美在线视频| 国内精品久久久久久久97牛牛| 麻豆精品在线视频| 欧美国产一区二区三区激情无套| 制服丝袜激情欧洲亚洲| 亚洲欧美日韩在线观看a三区| 在线观看精品| 一本大道av伊人久久综合| 国产在线精品一区二区夜色| 欧美成人按摩| 国产精品毛片大码女人| 欧美成人精品一区| 国产精品va在线播放| 欧美成人高清| 国产伦精品一区二区三区照片91| 免费观看久久久4p| 国产精品久久久久久久久借妻| 老**午夜毛片一区二区三区| 欧美久久久久久久久| 久久精品日韩一区二区三区| 欧美精品一区二区三区久久久竹菊 | 欧美一区激情视频在线观看| 99精品视频免费全部在线| 欧美亚洲一区二区在线| 99国产精品国产精品久久| 欧美在线视屏| 午夜精品视频在线观看| 欧美激情精品| 美日韩精品免费观看视频| 国产精品久久久久77777| 欧美黄色aa电影| 激情综合亚洲| 香港久久久电影| 在线综合亚洲欧美在线视频| 另类图片综合电影| 久久久久久久综合狠狠综合| 欧美日本韩国在线| 欧美成在线观看| 国产一在线精品一区在线观看| 一本一本久久| 一区二区三区日韩| 欧美成人嫩草网站| 欧美成人精品不卡视频在线观看| 国内成+人亚洲+欧美+综合在线| 国产精品99久久久久久久vr| 一区二区三区四区五区精品| 欧美精品一卡| 亚洲欧洲一区二区三区久久| 免费在线亚洲| 国产亚洲精品7777| 亚洲欧美一区在线| 欧美一区激情| 国产日韩在线一区二区三区| 羞羞答答国产精品www一本| 性久久久久久久久| 国产欧美精品一区二区色综合 | 欧美成人蜜桃| 亚洲人成在线观看网站高清| 欧美激情第六页| 亚洲国产精品一区二区第一页| 亚洲区免费影片| 欧美精品色综合| 亚洲精品在线免费| 亚洲欧美国产精品桃花| 国产精品一区二区你懂得| 欧美一区激情视频在线观看| 久久综合久久综合这里只有精品| 精品成人一区二区| 美女精品视频一区| 99精品热视频| 久久xxxx精品视频| 激情视频一区| 欧美国产视频一区二区| 一区二区三区欧美| 久久免费偷拍视频| 亚洲每日更新| 国产精品自拍一区| 久久综合狠狠| 99国产精品久久久久久久久久 | 亚洲日本欧美日韩高观看| 亚洲一区二区三区777| 国产精品视频精品| 久久夜色精品国产欧美乱| 亚洲精品日韩久久| 久久高清免费观看| 亚洲美女视频| 国产午夜精品全部视频在线播放 | 欧美日韩国产va另类| 午夜久久久久久| 亚洲国产1区| 性色av一区二区三区| 在线视频成人| 国产精品久久午夜| 免费亚洲电影| 午夜精品剧场| 亚洲人成高清| 久久综合伊人77777| 夜夜嗨av一区二区三区中文字幕 | 老色批av在线精品| 亚洲图片欧美日产| 亚洲国产日韩一区二区| 欧美一区二区三区久久精品茉莉花| 曰本成人黄色| 国产精品免费一区二区三区在线观看 | 国产麻豆精品theporn| 免费欧美日韩| 欧美在线视频二区| 亚洲视频在线一区| 国产精品萝li| 欧美国产欧美亚洲国产日韩mv天天看完整| 亚洲永久免费av| 91久久久久久久久| 麻豆精品精华液| 久久精品伊人| 欧美一级电影久久| 久久免费国产| 亚洲综合色自拍一区| 亚洲视频一区在线观看| 亚洲欧洲精品一区二区精品久久久| 欧美在线亚洲在线| 亚洲主播在线观看| 99国产精品99久久久久久粉嫩| 在线视频国内自拍亚洲视频| 国产一区二区日韩| 国产一区视频观看| 国产日韩一区欧美| 国产美女精品免费电影| 国产精品久久久久久影视| 欧美三级第一页| 欧美日韩在线观看一区二区| 欧美激情精品久久久久久变态| 欧美粗暴jizz性欧美20| 老司机免费视频一区二区三区| 久久久成人网| 久久午夜国产精品| 欧美成人嫩草网站| 欧美理论电影在线观看| 欧美日本乱大交xxxxx| 欧美激情一区二区三区蜜桃视频 | 99在线精品观看| 日韩一区二区免费看| 99视频热这里只有精品免费| 日韩视频一区二区三区| 99国产精品久久久久久久成人热| 日韩一区二区免费看| 亚洲性线免费观看视频成熟| 午夜欧美大片免费观看| 久久精品国产成人| 欧美二区在线播放| 欧美体内she精视频在线观看| 国产精品久久999| 国产酒店精品激情| 在线播放中文一区| 99精品国产热久久91蜜凸| 亚洲一二三区在线| 久久精品最新地址| 欧美黄色免费| 亚洲午夜久久久久久久久电影院| 午夜精品久久久久久久99水蜜桃| 久久久久九九视频| 欧美精品v日韩精品v韩国精品v| 国产精品theporn88| 黄色成人在线| 99人久久精品视频最新地址| 午夜精品福利一区二区蜜股av| 久久精品久久综合| 亚洲国产美女精品久久久久∴| 亚洲午夜激情免费视频| 久久久亚洲精品一区二区三区 | 欧美一级淫片aaaaaaa视频| 久久午夜电影网| 国产精品黄页免费高清在线观看| 激情婷婷欧美| 亚洲专区国产精品| 嫩草国产精品入口| 亚洲一区二区三区高清| 欧美www视频| 国产视频精品va久久久久久| 亚洲精品久久久久久下一站 | 亚洲欧洲99久久| 欧美国产精品劲爆| 亚洲欧美在线磁力| 欧美精品在欧美一区二区少妇| 韩国av一区二区三区四区| 亚洲深夜激情| 亚洲第一福利在线观看| 欧美亚洲自偷自偷| 国产精品久久久久久久久搜平片| 亚洲全黄一级网站| 老司机久久99久久精品播放免费| 亚洲午夜小视频|