• <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>
            posts - 7,comments - 3,trackbacks - 0

            Ice_cream’s world II

            Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
            Total Submission(s): 938    Accepted Submission(s): 192


            Problem Description
            After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.
             

            Input
            Every case have two integers N and M (N<=1000, M<=10000), the cities numbered 0…N-1, following M lines, each line contain three integers S, T and C, meaning from S to T have a road will cost C.
             

            Output
            If no location satisfy the queen’s require, you must be output “impossible”, otherwise, print the minimum cost in this project and suitable city’s number. May be exist many suitable cities, choose the minimum number city. After every case print one blank.
             

            Sample Input
            3 1 0 1 1 4 4 0 1 10 0 2 10 1 3 20 2 3 30
             

            Sample Output
            impossible 40 0
             

            Author
            Wiskey
             

            Source
             

            Recommend
            威士忌
             



            思路:不定根的最小樹形圖,做法就是虛擬一個根,讓所有點到這個根連線邊,并且邊權值很大,這樣就能保證最后只有一個點連向這個虛擬根,這樣最后結果減去這個很大值就行了。
            代碼:
            #include <cstdio>
            #include 
            <cstring>
            #include 
            <algorithm>
            #define MAXN 1010
            #define MAXE 10100
            using namespace std;

            typedef 
            long long typec;
            const typec INF = 0x7fffffffffffffffLL;

            struct Arcs
            {
                
            int _a, _b;
            } arcs[MAXE 
            + MAXN];

            struct AdjNode
            {
                
            int _v;
                Arcs 
            *_rf;
                typec _c;
                AdjNode 
            *_next;
            *adj[MAXN], adjmem[MAXE + MAXN];
             
            int adjcnt;
             
            inline 
            void init(int n)
            {
                memset(adj, 
            0, n * sizeof(AdjNode *));
                adjcnt 
            = 0;
            }
             
            inline 
            void add_edge(int a, int b, typec c)
            {
                arcs[adjcnt]._a 
            = a;
                arcs[adjcnt]._b 
            = b;
                AdjNode 
            *ptr = adjmem + adjcnt++;
                ptr 
            -> _c = c;
                ptr 
            -> _v = a;
                ptr 
            -> _rf = arcs + adjcnt - 1;
                ptr 
            -> _next = adj[b];
                adj[b] 
            = ptr;
            }
             
            int pre[MAXN], real_pre[MAXN];
            bool is_out[MAXN];
            int vis[MAXN], vcnt;
             
            typec solve(
            int n, int root)
            {
                
            static typec ch[MAXN];
                memset(is_out, 
            false, n);
                typec ans 
            = 0;
                
            while (1)
                {
                    
            int i, j, k;
                    
            for (i = 0; i < n; ++i)
                        
            if (i != root && !is_out[i])
                        {
                            pre[i] 
            = i;
                            ch[i] 
            = INF;
                            AdjNode 
            *chp;
                            
            for (AdjNode *ptr = adj[i]; ptr; ptr = ptr -> _next)
                            {
                                j 
            = ptr -> _v;
                                
            if (!is_out[j])
                                {
                                    
            if (ch[i] > ptr -> _c)
                                    {
                                        pre[i] 
            = j;
                                        ch[i] 
            = ptr -> _c;
                                        chp 
            = ptr;
                                    }
                                    
            else if (ch[i] == ptr -> _c && ptr -> _rf -> _a == root && ptr -> _rf -> _b < chp -> _rf -> _b)
                                    {
                                        pre[i] 
            = j;
                                        chp 
            = ptr;
                                    }
                                }
                            }
                            
            if (pre[i] == i) throw false;
                            real_pre[chp 
            -> _rf -> _b] = chp -> _rf -> _a;
                        }
                    memset(vis, 
            0, n * sizeof(int));
                    vcnt 
            = 0;
                    
            for (i = 0; i < n; ++i)
                        
            if (i != root && !is_out[i])
                        {
                            j 
            = i;
                            vis[i] 
            = ++ vcnt;
                            
            while (vis[pre[j]] == 0 && pre[j] != root)
                            {
                                j 
            = pre[j];
                                vis[j] 
            = vcnt;
                            }
                            
            if (vis[pre[j]] == vcnt)
                            {
                                i 
            = pre[j];
                                
            break;
                            }
                        }
                    
            if (i == n)
                    {
                        
            for (j = 0; j < n; ++j)
                            
            if (j != root && !is_out[j])
                                ans 
            += ch[j];
                        
            break;
                    }
                    j 
            = i;
                    
            ++vcnt;
                    
            int ti = i;
                    
            do
                    {
                        ti 
            = min(ti, j);
                        vis[j] 
            = vcnt;
                        is_out[j] 
            = true;
                        ans 
            += ch[j];
                        j 
            = pre[j];
                    }
                    
            while (j != i);
                    i 
            = ti;
                    
            for (j = 0; j < n; ++j)
                        
            if (vis[j] == vcnt)
                            
            for (AdjNode **ptr = adj + j; *ptr;)
                            {
                                k 
            = (*ptr) -> _v;
                                
            if (!is_out[k])
                                {
                                    AdjNode 
            *p2 = *ptr;
                                    p2 
            -> _c -= ch[j];
                                    
            if (i != j)
                                    {
                                        
            *ptr = p2 -> _next;
                                        p2 
            -> _next = adj[i];
                                        adj[i] 
            = p2;
                                    }
                                    
            else
                                        ptr 
            = &((*ptr) -> _next);
                                }
                                
            else
                                    ptr 
            = &((*ptr) -> _next);
                            }
                    
            for (k = 0; k < n; ++k)
                        
            if (!is_out[k])
                            
            for (AdjNode *ptr = adj[k]; ptr; ptr = ptr -> _next)
                            {
                                j 
            = ptr -> _v;
                                
            if (vis[j] == vcnt)
                                    ptr 
            -> _v = i;
                            }
                    is_out[i] 
            = false;
                }
                
            return ans;
            }
             
            int main()
            {
                
            int n, m;
                
            while (scanf("%d%d"&n, &m) != EOF)
                {
                    init(n 
            + 1);
                    
            long long s = 1;
                    
            for (int i = 0; i < m; ++i)
                    {
                        
            int a, b, c;
                        scanf(
            "%d%d%d"&a, &b, &c);
                        
            if (a != b)
                        {
                            add_edge(a, b, c);
                            s 
            += c;
                        }
                    }
                    
            for (int i = 0; i < n; ++i)
                        add_edge(n, i, s);
                    
            long long ans = solve(n + 1, n);
                    
            int r, p;
                    
            for (r = 0; real_pre[r] != n; ++r);
                    
            for (p = r + 1; p < n; ++p)
                        
            if (real_pre[p] == n)
                            
            break;
                    
            if (p == n)
                        printf(
            "%I64d %d\n\n", ans - s, r);
                    
            else
                        printf(
            "impossible\n\n");
                }
                
            return 0;
            }
             
            posted on 2011-10-15 22:18 LLawliet 閱讀(256) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            久久精品亚洲一区二区三区浴池| 亚洲精品乱码久久久久久蜜桃图片 | 中文字幕无码免费久久| 无码伊人66久久大杳蕉网站谷歌| 国内精品久久久久久99蜜桃| 国产精品久久久久一区二区三区| 亚洲欧美国产日韩综合久久| 久久久久久久久久久久中文字幕 | 免费观看成人久久网免费观看| 精品久久久久中文字幕一区| 久久久久久久波多野结衣高潮| 久久国产一区二区| 久久AV高潮AV无码AV| 狠狠综合久久综合中文88| 亚洲国产精品无码久久久不卡| 久久精品国产亚洲5555| 91久久精一区二区三区大全| 久久久这里有精品| 精品99久久aaa一级毛片| 亚洲精品国产美女久久久| 精品久久人人爽天天玩人人妻| 久久99国产综合精品免费| 亚洲欧洲精品成人久久奇米网| 97久久超碰国产精品旧版| 国产色综合久久无码有码| 久久久久久久久久免免费精品| 72种姿势欧美久久久久大黄蕉| 亚洲综合日韩久久成人AV| 区亚洲欧美一级久久精品亚洲精品成人网久久久久 | 亚洲精品97久久中文字幕无码| 亚洲成色999久久网站| …久久精品99久久香蕉国产| 久久无码专区国产精品发布| 性高湖久久久久久久久AAAAA| 国产精品xxxx国产喷水亚洲国产精品无码久久一区 | 亚洲色欲久久久久综合网| 精品国产婷婷久久久| 久久99精品久久久久久水蜜桃| 久久夜色精品国产亚洲| 91超碰碰碰碰久久久久久综合| 久久91精品久久91综合|