• <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 閱讀(254) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
            久久综合九色综合网站| 国产亚洲美女精品久久久久狼| 久久综合丝袜日本网| 伊人久久精品无码二区麻豆| 国内精品久久久久影院网站| 老司机国内精品久久久久| 7国产欧美日韩综合天堂中文久久久久| 久久受www免费人成_看片中文| 久久精品国产只有精品2020| 日韩十八禁一区二区久久| 免费精品99久久国产综合精品| 亚洲精品第一综合99久久| 国产一区二区精品久久凹凸| 亚洲欧美久久久久9999| 久久久久久久亚洲精品 | 日韩AV无码久久一区二区| 久久久久久精品久久久久| 久久天天躁狠狠躁夜夜不卡| 香港aa三级久久三级老师2021国产三级精品三级在 | 久久久久久九九99精品| 久久国产精品99精品国产| 国产精品久久久久影视不卡| 久久精品久久久久观看99水蜜桃| 久久99精品国产麻豆宅宅| 99久久国产综合精品五月天喷水| 香蕉久久久久久狠狠色| 狠狠色丁香婷婷综合久久来来去| 久久精品国产亚洲AV蜜臀色欲| 99久久人人爽亚洲精品美女| 色老头网站久久网| 欧美日韩精品久久久免费观看| 久久久久久精品久久久久| 亚洲国产精品18久久久久久| 精品国产99久久久久久麻豆| 香蕉久久夜色精品国产小说| 国产亚洲美女精品久久久久狼| 久久久网中文字幕| 亚洲精品久久久www| 国内精品久久久久久久久电影网 | 久久香蕉国产线看观看99| 久久久久99精品成人片|