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

            poj1201

            Intervals

            Time Limit: 2000MS Memory Limit: 65536K
            Total Submissions: 15733 Accepted: 5871

            Description

            You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
            Write a program that:
            reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
            computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
            writes the answer to the standard output.

            Input

            The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals. The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai, bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

            Output

            The output contains exactly one integer equal to the minimal size of set Z sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.

            Sample Input

            5
            3 7 3
            8 10 3
            6 8 1
            1 3 1
            10 11 1

            Sample Output

            6
            這題最多可能有5w的點,但是給的邊數有5w
            而且要注意的是 對每個區間[i-1,i]都有>=0 <=1的條件
            如果直接建圖的話,邊數可能有15w
            所以時間上bellman_ford 可能很難承受
            所有要優化
            對于那些默認的條件,顯然我們可以不用把這些邊加進去,
            在每次判斷時候,判斷一邊即可
            對于bellman_ford 還有優化是,如果一次循環中沒有修改任何值,則說明bellman_ford已經得到解了,
            沒必要繼續執行了 直接推出就行了
            目標是求dist[mx]-dist[mn]
            #include<algorithm>
            #include
            <iostream>
            #include
            <cstring>
            #include
            <cstdio>
            #include
            <cstdlib>
            #include
            <string>
            #include
            <cmath>
            using namespace std;
            #define inf 0x7ffffff
            #define max 50004
            struct node 
            {
                
            int u,v,w;
            }
            edge[max];
            int n,dist[max],mn,mx;
            void init()
            {
                
            int i;
                
            for(i=0;i<max;i++) dist[i]=0;
                mx
            =1;mn=inf;
            }

            void bellman_ford()
            {
                
            int k,t;
                
            bool flag=true;
                
            while(flag)
                
            {
                    flag
            =false;
                    
            for(k=0;k<n;k++)
                    
            {
                        t
            =dist[edge[k].u]+edge[k].w;
                        
            if (dist[edge[k].v]>t)
                        
            {
                            dist[edge[k].v]
            =t;
                            flag
            =true;
                        }

                    }

                    
            for(k=mn;k<mx;k++)
                    
            {
                        t
            =dist[k-1]+1;
                        
            if (dist[k]>t)
                        
            {
                            dist[k]
            =t;
                            flag
            =true;
                        }

                    }

                    
            for(k=mn;k<mx;k++)
                    
            {
                        
            if (dist[k-1]>dist[k])
                        
            {
                            dist[k
            -1]=dist[k];
                            flag
            =true;
                        }

                    }

                }

            }

            int main()
            {
                
            int i,u,v,w;
                
            while (scanf("%d",&n)!=EOF)
                
            {
                    
            for(i=0;i<n;i++)
                    
            {
                        scanf(
            "%d%d%d",&u,&v,&w);
                        edge[i].u
            =v;
                        edge[i].v
            =u-1;
                        edge[i].w
            =-w;
                        
            if (u<mn)
                        
            {
                            mn
            =u;
                        }

                        
            if (v>mx)
                        
            {
                            mx
            =v;
                        }

                    }

                    bellman_ford();
                    printf(
            "%d\n",dist[mx]-dist[mn-1]);
                }

                
            return 0;
            }

            posted on 2012-04-03 17:38 jh818012 閱讀(187) 評論(0)  編輯 收藏 引用

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿

            文章檔案(85)

            搜索

            最新評論

            • 1.?re: poj1426
            • 我嚓,,輝哥,,居然搜到你的題解了
            • --season
            • 2.?re: poj3083
            • @王私江
              (8+i)&3 相當于是 取余3的意思 因為 3 的 二進制是 000011 和(8+i)
            • --游客
            • 3.?re: poj3414[未登錄]
            • @王私江
              0ms
            • --jh818012
            • 4.?re: poj3414
            • 200+行,跑了多少ms呢?我的130+行哦,你菜啦,哈哈。
            • --王私江
            • 5.?re: poj1426
            • 評論內容較長,點擊標題查看
            • --王私江
            久久99精品久久久久婷婷| 色偷偷偷久久伊人大杳蕉| 国产亚洲精品美女久久久| 精品熟女少妇AV免费久久| 国产亚洲精品久久久久秋霞 | 久久亚洲精品中文字幕| 久久久亚洲欧洲日产国码二区 | 久久99热这里只有精品国产| 久久人人爽人人人人爽AV| 久久一日本道色综合久久| 久久精品国产亚洲7777| 久久天天躁狠狠躁夜夜不卡| 久久久久久久久波多野高潮| 青草影院天堂男人久久| 亚洲va久久久久| 久久99热国产这有精品| 午夜精品久久久久久中宇| 无码8090精品久久一区| 国产精品久久国产精品99盘 | 国产精品成人久久久久久久| 国产一区二区三区久久精品| 色婷婷噜噜久久国产精品12p| aaa级精品久久久国产片| 国产精品乱码久久久久久软件 | 国产99久久久国产精免费| 伊人久久综合成人网| 无码任你躁久久久久久久| 国产精品内射久久久久欢欢| 97久久久精品综合88久久| 中文字幕热久久久久久久| 久久精品女人天堂AV麻| 久久精品无码一区二区三区免费| 好属妞这里只有精品久久| 狠狠色丁香婷综合久久| 国产亚洲色婷婷久久99精品| 欧美亚洲色综久久精品国产| 一本久久a久久精品vr综合| 伊人久久综合无码成人网| 无码日韩人妻精品久久蜜桃| 久久妇女高潮几次MBA| 久久丫精品国产亚洲av不卡|