青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(266) 評論(0)  編輯 收藏 引用 所屬分類: 圖論
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            亚洲网站啪啪| 欧美专区日韩视频| 欧美视频国产精品| 亚洲一区二区成人在线观看| 9久re热视频在线精品| 欧美性淫爽ww久久久久无| 亚洲欧美日韩一区二区| 亚洲综合另类| 一区二区三区在线视频观看| 欧美黄色视屏| 国产精品国产三级国产aⅴ无密码 国产精品国产三级国产aⅴ入口 | 欧美激情国产精品| 亚洲无玛一区| 欧美影院视频| 亚洲人体大胆视频| 亚洲午夜精品网| 激情欧美一区二区三区在线观看| 亚洲国产高潮在线观看| 欧美日韩精品伦理作品在线免费观看| 亚洲在线成人| 久久综合图片| 欧美一级淫片播放口| 久久综合九色| 午夜精品久久久久久久久久久久| 久久久久一本一区二区青青蜜月| 一级日韩一区在线观看| 欧美一区二区三区免费在线看 | 欧美精品v国产精品v日韩精品| 亚洲影院在线| 美女诱惑黄网站一区| 午夜精品免费在线| 欧美二区不卡| 另类图片综合电影| 国产精品午夜国产小视频| 欧美激情第4页| 国产主播精品| 亚洲无线观看| 一本一道久久综合狠狠老精东影业| 欧美亚洲在线播放| 亚洲免费影视第一页| 免费观看成人| 玖玖综合伊人| 国产一区二区三区久久久| 亚洲视频在线看| 在线一区二区三区做爰视频网站 | 午夜免费日韩视频| 亚洲综合不卡| 欧美日韩视频在线一区二区 | 久久精品夜夜夜夜久久| 欧美在线观看网站| 国产精品美女视频网站| 一二三四社区欧美黄| 亚洲美女中文字幕| 嫩草影视亚洲| 欧美国产欧美亚洲国产日韩mv天天看完整 | 久久久久国产精品一区二区| 午夜精品久久久久久久久久久久久 | 亚洲视频999| 亚洲一区二区高清| 欧美少妇一区二区| 日韩视频一区二区三区在线播放免费观看| 在线播放亚洲一区| 久久午夜激情| 亚洲电影免费在线观看| 91久久久一线二线三线品牌| 久久久天天操| 欧美国产另类| 99亚洲一区二区| 欧美精品一区二区三区在线看午夜 | 亚洲小视频在线| 国产精品高清免费在线观看| 亚洲天堂av在线免费| 欧美在线视频不卡| 激情综合色综合久久综合| 老色鬼久久亚洲一区二区| 亚洲国产福利在线| 亚洲天天影视| 国产一区 二区 三区一级| 久久福利毛片| 亚洲国产精品va在线观看黑人| 亚洲日本va午夜在线影院| 欧美日韩精品| 欧美一级免费视频| 欧美激情一区在线| 亚洲一区3d动漫同人无遮挡| 国产女人18毛片水18精品| 久久尤物视频| 日韩亚洲一区二区| 久久久激情视频| 亚洲人体一区| 国产伦精品一区二区| 榴莲视频成人在线观看| 一本色道**综合亚洲精品蜜桃冫 | 亚洲毛片一区二区| 国产精品一香蕉国产线看观看| 久久精品在线播放| 亚洲精一区二区三区| 欧美在线国产精品| 亚洲人成网在线播放| 国产精品免费在线| 欧美插天视频在线播放| 亚洲免费视频网站| 亚洲国产成人在线播放| 小嫩嫩精品导航| 亚洲精品一区二区三区av| 国产老女人精品毛片久久| 欧美不卡三区| 久久精品国产99精品国产亚洲性色| 亚洲国产精品免费| 久久久久久久综合日本| 一本色道久久综合精品竹菊 | 亚洲手机在线| 亚洲激情在线激情| 国产三级欧美三级日产三级99| 欧美黄色视屏| 葵司免费一区二区三区四区五区| 亚洲一区视频在线观看视频| 亚洲国产精品v| 免费一区视频| 久久青草久久| 欧美一级夜夜爽| 亚洲综合999| 一本色道婷婷久久欧美| 91久久久久久久久久久久久| 国产主播一区二区| 国产精品免费在线| 欧美视频免费在线| 欧美日韩国产在线看| 欧美xx视频| 欧美成人午夜剧场免费观看| 久久久欧美一区二区| 久久久久国产一区二区| 欧美一区二区三区视频在线| 午夜一区二区三区不卡视频| 亚洲午夜一区| 亚洲一区二区三区免费观看| 在线亚洲观看| 亚洲你懂的在线视频| 亚洲一区二区三| 亚洲综合国产| 香蕉久久夜色精品国产使用方法| 亚洲一区二区在线观看视频| 一区二区精品在线| 亚洲图片欧美一区| 亚洲一区二区毛片| 欧美一级久久| 久久网站免费| 免费毛片一区二区三区久久久| 欧美/亚洲一区| 欧美另类极品videosbest最新版本| 欧美成人一区二区三区片免费| 欧美成人精品福利| 欧美精品在线一区| 国产精品久久久久免费a∨大胸| 国产精品久久久久久久电影| 国产欧美日韩亚州综合| 国产亚洲女人久久久久毛片| 精品av久久707| 亚洲精品系列| 小嫩嫩精品导航| 美女日韩在线中文字幕| 亚洲全部视频| 亚洲视频在线看| 久久精品国产69国产精品亚洲| 老牛影视一区二区三区| 欧美日韩系列| 国产一区二区三区直播精品电影| 伊人狠狠色j香婷婷综合| 亚洲免费电影在线观看| 亚洲一区二区三区国产| 久久久免费精品| 亚洲三级电影在线观看| 亚洲综合导航| 欧美成人精品不卡视频在线观看| 欧美性事在线| 亚洲国产日韩一级| 午夜精品一区二区三区四区 | 欧美在线黄色| 亚洲欧洲精品一区| 欧美在线观看一区二区| 欧美精品久久久久久久久老牛影院| 国产精品视频网站| 亚洲欧洲综合另类| 欧美一区免费| 亚洲美女精品久久| 久久高清免费观看| 欧美亚洲成人网| 亚洲国产精品一区二区www在线| 亚洲欧美日韩国产精品| 亚洲国产免费看| 欧美一级专区| 国产精品国产三级国产专播精品人| 亚洲国产成人一区| 久久久久久网| 午夜精品亚洲| 国产精品成人一区二区艾草| 91久久夜色精品国产网站| 久热精品在线视频| 先锋影音国产一区| 国产精品嫩草久久久久|