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

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            hdu 2419 (STL:set multiset)

            首先膜拜膜拜青島二中的 aKc大牛啊,我徹底給跪了?。?!
            差距太大,好好努力吧!??!

            算法,數據結構,C++,STL。需要去學的啊,下午開始學吧學吧

            圖的操作,使用集合來維護,把操作序列倒過來看,割邊則看做兩個集合的合并。

            STL 的set和multiset 很強大啊,第一用STL寫東西

            wangs ,你該努力了,大牛之路,遠著呢。
            #include <cstdlib>
            #include 
            <cctype>
            #include 
            <cstring>
            #include 
            <cstdio>
            #include 
            <cmath>
            #include 
            <algorithm>
            #include 
            <vector>
            #include 
            <string>
            #include 
            <iostream>
            #include 
            <sstream>
            #include 
            <map>
            #include 
            <set>
            #include 
            <queue>
            #include 
            <stack>
            #include 
            <fstream>
            #include 
            <numeric>
            #include 
            <iomanip>
            #include 
            <bitset>
            #include 
            <list>
            #include 
            <stdexcept>
            #include 
            <functional>
            #include 
            <utility>
            #include 
            <ctime>
            #include 
            <cmath>
            #include 
            <climits>

            using namespace std;

            typedef pair
            <intint> PII;
            const int MAXN = 20010, MAXM = 60010, MAXQ = 300010;
            int value[MAXN], query[MAXQ][3];
            multiset
            <PII> e;
            multiset
            <int> v[MAXN];
            int pre[MAXN];

            int root(int a)
            {
                
            if(pre[a] != a)
                    pre[a] 
            = root(pre[a]);
                
            return pre[a];
            }

            int unionSet(int a, int b)
            {
                multiset
            <int>::iterator it;
                a 
            = root(a), b = root(b);
                
            if(a == b)
                    
            return 0;
                
            if(v[a].size() > v[b].size())
                    swap(a, b);
                
            for    (it = v[a].begin(); it != v[a].end(); it++)
                    v[b].insert(
            *it);
                v[a].clear();
                pre[a] 
            = b;
                
            return 0;
            }

            int update(int a, int x)
            {
                
            int ta = a;
                a 
            = root(a);
                v[a].erase(v[a].find(value[ta]));
                v[a].insert(x);
                value[ta] 
            = x;
                
            return 0;
            }

            int main()
            {
                
            int n, m, q;
                
            int a, b;
                
            int i,u;
                
            int cas=0;
                
            char ch[3];
                
            double ct = 0, sum = 0;
                multiset
            <PII>::iterator it;
                multiset
            <int>::iterator tp;
                
            while(scanf("%d%d%d",&n,&m,&q)==3)
                {
                    e.clear();
                    
            for (i = 1; i <= n; i++)
                        v[i].clear();

                    
            for (i = 1; i <= n; i++)
                    {
                        scanf(
            "%d"&value[i]);
                        pre[i] 
            = i;
                    }
                    
            for (i = 0; i < m; i++)
                    {
                        scanf(
            "%d%d"&a, &b);
                        
            if(a > b)
                            swap(a, b);
                        e.insert(PII(a, b));
                    }

                    
            for (i = 0; i < q; i++)
                    {
                        scanf(
            "%s"&ch);
                        scanf(
            "%d%d"&query[i][1], &query[i][2]);

                        query[i][
            0= ch[0];
                        
            if(ch[0== 'E')
                        {
                            
            if(query[i][1> query[i][2])
                                swap(query[i][
            1], query[i][2]);

                            it 
            = e.find(PII(query[i][1], query[i][2]));
                            e.erase(it);
                        }
                        
            else if(ch[0== 'U')
                            swap(value[query[i][
            1]], query[i][2]);
                    }

                    
            for (i = 1; i <= n; i++)
                        v[i].insert(value[i]);
                    
            for (it = e.begin(); it != e.end(); it++)
                        unionSet(it
            ->first, it->second);

               
            //     for (it = e.begin(); it != e.end(); it++)
                
            //        printf("%d %d\n",it->first, it->second);

                    ct
            =0;
                    sum
            =0;

                    
            for(int i = q - 1; i >= 0; i--)
                    {
                        
            if(query[i][0== 'E')
                            unionSet(query[i][
            1], query[i][2]);
                        
            else if(query[i][0== 'U')
                            update(query[i][
            1], query[i][2]);
                        
            else
                        {
                            ct 
            += 1;
                            u 
            = root(query[i][1]);
                            tp 
            = v[u].lower_bound(query[i][2]);
                            
            if(tp != v[u].end())
                                sum 
            += *tp;
                      
            //      printf("%d %d\n",u,*tp);
                        }
                    }
                    printf(
            "Case %d: %0.3lf\n",++cas,(double)sum/ct);
                }
                
            return 0;
            }

            posted on 2012-07-14 13:08 wangs 閱讀(267) 評論(0)  編輯 收藏 引用 所屬分類: ACM-數據結構

            久久国产亚洲精品| 久久受www免费人成_看片中文| 人妻无码中文久久久久专区| 亚洲中文字幕久久精品无码喷水| 久久精品国产99国产精品亚洲| 久久午夜羞羞影院免费观看| 国产成人久久777777| 无码乱码观看精品久久| 久久精品国产清高在天天线| 久久99精品久久久久久水蜜桃 | 人妻精品久久久久中文字幕69| 99久久超碰中文字幕伊人| 国产精品免费久久久久电影网| 久久婷婷人人澡人人爽人人爱| 久久99精品国产麻豆| 久久这里的只有是精品23| 久久精品国产99国产精品澳门 | 久久久久久久97| 欧美精品一区二区久久| 久久免费国产精品一区二区| 久久精品国产亚洲AV不卡| 久久国产精品免费一区| 狠狠狠色丁香婷婷综合久久五月 | 久久综合亚洲色HEZYO社区| 亚洲狠狠久久综合一区77777| 久久久久人妻一区精品性色av| 久久人做人爽一区二区三区| 欧美久久久久久午夜精品| 国产2021久久精品| 精品久久香蕉国产线看观看亚洲| 亚洲国产精品无码久久久不卡| 色综合久久夜色精品国产| 亚洲精品国产自在久久| 久久久久久极精品久久久| 久久国产视屏| 开心久久婷婷综合中文字幕| 久久99国产一区二区三区| 午夜精品久久久久久影视777 | 亚洲成色999久久网站| 国产高清美女一级a毛片久久w| 久久免费高清视频|