• <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算法程序設計空間

            // 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 閱讀(3128) 評論(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
            看看!!!
            日韩精品国产自在久久现线拍| 亚洲AV无码1区2区久久 | 九九精品99久久久香蕉| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 精品久久久久久无码专区| 久久精品欧美日韩精品| 久久99精品九九九久久婷婷 | 久久99热这里只频精品6| 国产亚洲精品久久久久秋霞| 精品久久久久久综合日本| 精品一久久香蕉国产线看播放 | 久久人人爽人人人人爽AV | 亚洲AⅤ优女AV综合久久久| 午夜肉伦伦影院久久精品免费看国产一区二区三区 | 久久久噜噜噜www成人网| 久久91这里精品国产2020| 亚洲人成网亚洲欧洲无码久久| 国产精品久久久久…| 久久亚洲国产精品五月天婷| 97精品国产91久久久久久| 亚洲色大成网站www久久九| 国产香蕉97碰碰久久人人| 久久久免费精品re6| 国产69精品久久久久APP下载| 久久se精品一区精品二区国产| 18禁黄久久久AAA片| 99久久夜色精品国产网站| 国产亚洲精品久久久久秋霞 | 偷偷做久久久久网站| 精品免费久久久久国产一区| 精品综合久久久久久97超人 | 一级做a爱片久久毛片| 久久久久九国产精品| 久久国产亚洲精品麻豆| 99久久精品费精品国产一区二区| 久久精品视频一| 思思久久好好热精品国产| 色青青草原桃花久久综合| 伊人色综合久久天天网 | 97精品伊人久久大香线蕉app| 国内精品伊人久久久影院|