• <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免费久久 | 色综合久久天天综线观看| 大香网伊人久久综合网2020| 国产精品一区二区久久| 91久久九九无码成人网站 | 久久丫精品国产亚洲av| 精品无码久久久久久尤物| 国产成人久久777777| 欧美日韩精品久久久免费观看| 亚洲国产精品高清久久久| 91精品国产高清久久久久久91| 日本欧美国产精品第一页久久| 亚洲国产精品久久久天堂| 国内精品久久久久久久coent| 蜜桃麻豆WWW久久囤产精品| 91精品国产综合久久香蕉| 久久精品视频一| 亚洲伊人久久大香线蕉苏妲己| 无码任你躁久久久久久老妇App| 99久久国产综合精品麻豆| 久久精品国产精品亚洲精品| 亚洲综合精品香蕉久久网97| 久久亚洲精品成人av无码网站| 久久精品不卡| 日韩精品国产自在久久现线拍 | 国产精品久久新婚兰兰| 91麻豆精品国产91久久久久久| 国产成人精品综合久久久久 | 狠狠色伊人久久精品综合网| 成人妇女免费播放久久久| 久久婷婷五月综合97色直播| 久久久久久无码国产精品中文字幕 | 日韩人妻无码精品久久免费一| 色播久久人人爽人人爽人人片aV| 国产成人精品久久二区二区 | 国产精品99久久久久久www| 91精品国产乱码久久久久久| 久久久无码人妻精品无码| 人妻丰满AV无码久久不卡| 久久天天躁狠狠躁夜夜网站| 国产成人无码精品久久久性色|