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

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

// 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) 評論(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回路。
典型的參數(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ù)  更多評論   

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

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

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

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

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

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

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ù)  更多評論   

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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久久精品国产| 国产亚洲亚洲| 亚洲一区二区动漫| 一二三区精品福利视频| 国产精品地址| 久久久在线视频| 久久久久久久久综合| 亚洲黄色免费| 一本在线高清不卡dvd| 国产精品青草久久久久福利99| 欧美中文字幕在线播放| 久久久欧美精品sm网站| 日韩视频精品| 亚洲伊人观看| 在线观看成人av| 一区二区福利| 尤妮丝一区二区裸体视频| 亚洲破处大片| 国产精品一区视频| 欧美韩国一区| 国产精品视频xxxx| 亚洲第一页在线| 国产精品老牛| 亚洲国产视频一区二区| 国产精品日韩欧美大师| 亚洲成人在线网| 国产女人精品视频| 欧美国产一区视频在线观看| 国产精品av久久久久久麻豆网| 久久精品视频在线| 欧美日韩亚洲不卡| 欧美国产第二页| 国产精品一区二区欧美| 亚洲欧洲在线视频| 狠狠色噜噜狠狠色综合久| 99国产精品| 91久久精品美女高潮| 午夜视频在线观看一区| 国产精品99久久99久久久二8| 久久精品一区二区三区四区 | 国产欧美高清| 亚洲美洲欧洲综合国产一区| 一区二区三区在线免费播放| 亚洲一区在线播放| 亚洲午夜av在线| 欧美国产日本韩| 免费在线观看成人av| 国产亚洲第一区| 亚洲一二三四区| 亚洲一区二区av电影| 欧美激情乱人伦| 亚洲黄色毛片| 亚洲人成久久| 免播放器亚洲| 欧美国产日韩一二三区| 亚洲成人原创| 久久免费视频在线观看| 久久久久国色av免费看影院| 国产精品视频区| 亚洲综合色在线| 欧美一区二区三区免费观看视频| 国产精品二区在线| 亚洲小少妇裸体bbw| 亚洲欧美日韩国产一区二区三区| 欧美四级伦理在线| 亚洲午夜日本在线观看| 欧美在线播放高清精品| 国产亚洲电影| 久久久久网址| 亚洲第一二三四五区| 亚洲精品国产视频| 欧美日韩国产另类不卡| 99这里只有精品| 欧美一级专区| 精品二区视频| 欧美精品久久久久久久久久| 日韩视频免费观看| 欧美一区2区视频在线观看 | 欧美理论电影网| 正在播放欧美一区| 久久久另类综合| 亚洲欧洲一区| 欧美日韩中文字幕日韩欧美| 亚洲综合首页| 快播亚洲色图| 亚洲天堂成人在线观看| 国产欧美日韩免费| 免费久久精品视频| 亚洲素人一区二区| 久久综合国产精品| 一区二区三区四区五区视频| 国产精品自拍小视频| 久久人人爽国产| av成人黄色| 美女福利精品视频| 亚洲天堂第二页| 影音先锋亚洲一区| 国产精品激情电影| 免费中文日韩| 午夜视频久久久| 亚洲国产日韩欧美在线动漫| 欧美影院一区| 99国产麻豆精品| 合欧美一区二区三区| 欧美日韩一区二区三| 久久久777| 在线中文字幕日韩| 亚洲高清一二三区| 久久免费精品日本久久中文字幕| 一本色道久久综合亚洲精品婷婷 | 亚洲欧洲精品一区| 国产日韩成人精品| 欧美日韩午夜激情| 免费观看成人| 久久精品视频va| 亚洲一区在线播放| 日韩视频免费观看高清在线视频 | 免费亚洲网站| 久久久久久久久一区二区| 亚洲一区二区三区久久| 最新亚洲视频| 影音先锋日韩资源| 国产亚洲精品美女| 国产九九精品| 国产精品久久久久免费a∨| 欧美成人免费小视频| 久久亚洲图片| 久久久噜噜噜久久狠狠50岁| 亚洲在线成人| 亚洲综合国产| 亚洲一区二区av电影| 一本色道久久综合狠狠躁篇的优点 | 久热爱精品视频线路一| 久久高清福利视频| 欧美在线不卡| 久久久久久亚洲精品中文字幕| 午夜影视日本亚洲欧洲精品| 亚洲综合色在线| 亚洲一区一卡| 午夜视黄欧洲亚洲| 欧美一区二区女人| 欧美自拍偷拍午夜视频| 久久精品亚洲精品| 久久女同互慰一区二区三区| 久久综合国产精品| 免费亚洲一区二区| 亚洲激情小视频| 日韩小视频在线观看| 亚洲性线免费观看视频成熟| 亚洲伊人伊色伊影伊综合网| 亚洲欧美日韩国产成人精品影院| 先锋影音一区二区三区| 欧美在线观看视频在线| 久久婷婷蜜乳一本欲蜜臀| 欧美国产欧美亚洲国产日韩mv天天看完整 | 久久久久久穴| 欧美成人中文字幕在线| 欧美日韩国产不卡在线看| 国产精品久久久久久久第一福利 | 国产精品男人爽免费视频1| 国产精品一区二区三区乱码| 国产亚洲福利社区一区| 亚洲国产日韩在线| 亚洲一区二区三区乱码aⅴ蜜桃女| 亚洲欧美综合精品久久成人| 久久久亚洲成人| 亚洲精品欧美日韩专区| 午夜精品www| 免费日韩成人| 国产精品视频久久一区| 精品福利免费观看| 在线亚洲成人| 久久在线播放| 亚洲毛片播放| 久久精品视频99| 国产精品h在线观看| 欲色影视综合吧| 亚洲欧美视频在线| 亚洲第一在线| 亚洲欧美日韩综合| 欧美精品福利视频| 黑人中文字幕一区二区三区| 一区二区三区四区在线| 麻豆成人av| 亚洲一区在线视频| 欧美精品播放| 亚洲成人原创| 久久精品亚洲一区二区三区浴池| 亚洲国产小视频在线观看| 午夜精品婷婷| 国产精品www| 亚洲精品国产精品国自产在线 | 91久久精品日日躁夜夜躁国产| 亚洲欧美日韩一区二区在线 | 亚洲视频一区在线| 欧美激情日韩| 久久亚裔精品欧美| 国产一区二区丝袜高跟鞋图片| 在线中文字幕一区| 91久久黄色|