• <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
            威士忌
             



            思路:不定根的最小樹形圖,做法就是虛擬一個(gè)根,讓所有點(diǎn)到這個(gè)根連線邊,并且邊權(quán)值很大,這樣就能保證最后只有一個(gè)點(diǎn)連向這個(gè)虛擬根,這樣最后結(jié)果減去這個(gè)很大值就行了。
            代碼:
            #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) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 圖論
            久久久国产乱子伦精品作者| 青青青国产精品国产精品久久久久| 国产毛片久久久久久国产毛片| 久久久精品视频免费观看| 亚洲日韩欧美一区久久久久我| 久久伊人五月丁香狠狠色| 精品久久久久久无码中文字幕一区| 久久九九全国免费| 久久久久亚洲AV成人网人人网站| 久久亚洲欧美国产精品| 久久午夜综合久久| 国产一区二区精品久久| 久久亚洲精品无码aⅴ大香| 久久亚洲国产中v天仙www| 亚洲?V乱码久久精品蜜桃| 国产精品久久久久9999高清| 久久综合亚洲鲁鲁五月天| 办公室久久精品| 91精品国产综合久久久久久| 久久人人爽人人爽人人片AV东京热| 久久超碰97人人做人人爱| 欧美日韩精品久久久免费观看| 激情五月综合综合久久69| 狠狠色丁香婷综合久久| 色欲av伊人久久大香线蕉影院| 久久伊人五月天论坛| 国产精品无码久久久久| 久久精品国产99国产精品澳门| 人妻精品久久无码区| 久久精品国产亚洲AV不卡| 久久WWW免费人成一看片| 一级a性色生活片久久无| 久久精品成人影院| 久久久久久久亚洲精品| 久久久亚洲精品蜜桃臀| 久久99精品国产麻豆不卡| 久久精品这里只有精99品| 国产精品美女久久久免费| 久久国产高清一区二区三区| 久久久久国产一级毛片高清版| 青青热久久综合网伊人|