• <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>

            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 閱讀(3129) 評(píng)論(14)  編輯 收藏 引用 所屬分類(lèi): ACM/ICPC或其他比賽

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

            后來(lái)從HUST上面找了道類(lèi)似的題目,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頁(yè)
            3.地震--最有比率生成樹(shù) 一節(jié)的解答
            和這個(gè)非常類(lèi)似

            就是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)小問(wè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)問(wèn)題,最后果然只有4.5分,和沒(méi)做沒(méi)區(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)問(wèn)這題你用隊(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
            看看!!!
            激情久久久久久久久久| 久久精品中文騷妇女内射| 久久www免费人成看国产片| 亚洲午夜无码久久久久小说| 久久精品无码一区二区无码| 久久国产成人亚洲精品影院| 精品综合久久久久久97| 国产成人精品综合久久久| 亚洲香蕉网久久综合影视| 中文字幕久久欲求不满| 久久精品人人做人人妻人人玩| 久久免费观看视频| 青青青青久久精品国产| 久久亚洲精品人成综合网| 香港aa三级久久三级老师2021国产三级精品三级在 | 久久综合给久久狠狠97色| 久久婷婷五月综合色99啪ak| 久久精品国产亚洲av水果派| 久久人人爽人人精品视频| 欧美久久综合性欧美| 人妻无码久久一区二区三区免费| 亚洲国产高清精品线久久| 久久国产精品二国产精品| 99久久亚洲综合精品网站| 26uuu久久五月天| 国产精品久久久99| 91精品婷婷国产综合久久| 久久久91精品国产一区二区三区| 久久精品国产精品亚洲毛片| 久久久久国产精品熟女影院| av无码久久久久不卡免费网站| 777午夜精品久久av蜜臀| 中文字幕无码免费久久| 亚洲精品乱码久久久久66| 乱亲女H秽乱长久久久| 99热成人精品热久久669| 久久国产免费观看精品| 久久99久久成人免费播放| 国产精品美女久久久久AV福利| 很黄很污的网站久久mimi色| 亚洲第一永久AV网站久久精品男人的天堂AV|