• <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-數據結構

            久久婷婷五月综合97色直播| 久久综合九色综合久99| 午夜精品久久久内射近拍高清| 久久亚洲精品无码观看不卡| 日批日出水久久亚洲精品tv| 久久香蕉超碰97国产精品| 好久久免费视频高清| 美女久久久久久| 欧美喷潮久久久XXXXx| 久久国产视频99电影| 蜜臀av性久久久久蜜臀aⅴ| 狠狠综合久久综合中文88| 无码人妻久久一区二区三区免费 | 久久精品国产精品亚洲毛片| 好久久免费视频高清| 久久久www免费人成精品| 成人a毛片久久免费播放| 亚洲av日韩精品久久久久久a | 99久久国产亚洲高清观看2024| 97精品伊人久久大香线蕉| 久久97精品久久久久久久不卡| 久久精品国产99国产精品导航| 国产精品无码久久综合网| 国产亚洲综合久久系列| 久久99热这里只有精品国产| 99久久夜色精品国产网站| 国产精品免费看久久久| 老色鬼久久亚洲AV综合| 久久精品国产亚洲AV香蕉| 麻豆久久久9性大片| 亚洲七七久久精品中文国产| 国产精品美女久久久久av爽| 国产精品久久自在自线观看| 久久精品中文闷骚内射| 久久九九精品99国产精品| 久久亚洲AV无码精品色午夜麻豆| 久久久精品久久久久久| 看全色黄大色大片免费久久久 | 一本久久a久久精品综合香蕉 | 99久久婷婷免费国产综合精品| 久久亚洲精品成人av无码网站|