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

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>
            久久精品中文字幕一区二区三区| 久久精品五月婷婷| 亚洲国产va精品久久久不卡综合| 亚洲欧美视频| 狠狠色丁香婷婷综合影院| 久久精品亚洲国产奇米99| 久久爱www| 亚洲国产一区二区三区青草影视| 欧美电影免费观看网站| 欧美激情欧美激情在线五月| 宅男在线国产精品| 亚洲资源av| 在线免费观看日韩欧美| 亚洲日本欧美天堂| 国产日韩欧美一区二区| 久久综合中文| 欧美日韩午夜视频在线观看| 欧美一级成年大片在线观看| 久久噜噜噜精品国产亚洲综合 | 中文亚洲字幕| 国外成人在线| 99人久久精品视频最新地址| 国产亚洲精品久久久久动| 国产精品毛片va一区二区三区 | 午夜在线一区二区| 亚洲美女色禁图| 欧美一区观看| 亚洲手机视频| 久久综合久久综合久久综合| 亚洲综合色网站| 久热精品视频在线观看| 性刺激综合网| 欧美日本三级| 欧美成人有码| 国产亚洲欧美激情| 夜夜嗨一区二区三区| 亚洲国产精品第一区二区| 亚洲欧美日韩电影| 亚洲一区二区免费视频| 老鸭窝91久久精品色噜噜导演| 午夜国产不卡在线观看视频| 欧美激情精品久久久六区热门| 久久激情视频久久| 国产精品久久久久久av下载红粉| 欧美肥婆在线| 在线免费高清一区二区三区| 亚洲男人的天堂在线aⅴ视频| 亚洲看片一区| 免费在线亚洲欧美| 男人的天堂成人在线| 韩日欧美一区二区三区| 亚洲欧美韩国| 欧美一区二区三区另类| 国产精品视频精品视频| 在线午夜精品自拍| 一区二区三区福利| 欧美日韩国产黄| 亚洲人成网站精品片在线观看| 亚洲第一页中文字幕| 久久久午夜视频| 美女视频黄a大片欧美| 激情婷婷欧美| 久久久久久久97| 免播放器亚洲| 亚洲人成网站在线播| 久久综合狠狠综合久久激情| 蜜桃av综合| 亚洲成色777777女色窝| 免费视频一区| 91久久极品少妇xxxxⅹ软件| av成人老司机| 欧美午夜激情视频| 亚洲欧美国内爽妇网| 久久九九热免费视频| 在线看日韩欧美| 欧美激情91| 中日韩午夜理伦电影免费| 亚洲一区免费网站| 国产欧美日韩综合一区在线播放| 性视频1819p久久| 免费高清在线一区| 亚洲精品国产视频| 国产精品久久国产精品99gif | 亚洲剧情一区二区| 亚洲欧美一区二区激情| 狠狠色狠狠色综合日日91app| 久久久最新网址| 日韩香蕉视频| 久久夜色精品国产亚洲aⅴ | 国产精品丝袜xxxxxxx| 久久精品亚洲一区二区三区浴池| 欧美国产日韩亚洲一区| 亚洲在线一区二区| 激情综合激情| 欧美午夜激情在线| 久久一区二区精品| 夜夜爽av福利精品导航| 久久中文字幕导航| 中文国产成人精品| 红桃视频亚洲| 国产精品久久| 久久这里有精品15一区二区三区| 日韩午夜中文字幕| 美女91精品| 午夜精品视频网站| 亚洲人成在线影院| 国产日本欧美一区二区三区| 欧美国产日韩一区二区在线观看 | 久久久91精品国产一区二区精品| 亚洲国产欧美在线人成| 国产伦精品一区二区三区免费 | 欧美日韩一级黄| 久久国产夜色精品鲁鲁99| 一区二区电影免费在线观看| 欧美成人亚洲成人| 久久久噜噜噜久久| 亚洲欧美日韩精品久久亚洲区| 亚洲国内在线| 一区精品在线| 国产人成精品一区二区三| 欧美日韩综合在线| 欧美国产精品| 蜜臀久久99精品久久久久久9| 亚洲欧美另类在线观看| 一区二区三区久久精品| 亚洲日本aⅴ片在线观看香蕉| 蜜桃av久久久亚洲精品| 久久久国产一区二区三区| 亚欧成人精品| 亚洲欧美日韩在线| 亚洲一区二区三区影院| 9l国产精品久久久久麻豆| 亚洲国产欧洲综合997久久| 好看不卡的中文字幕| 国产精品影片在线观看| 国产精品人成在线观看免费| 国产精品久久久亚洲一区 | 欧美理论电影网| 欧美国产一区二区在线观看| 美女免费视频一区| 欧美.日韩.国产.一区.二区| 久久综合色播五月| 免费成人av在线| 欧美成人免费网| 99精品免费视频| 亚洲九九爱视频| 亚洲一区二区三区视频播放| 亚洲视频欧美在线| 午夜久久电影网| 久久久久天天天天| 免费日韩精品中文字幕视频在线| 欧美va天堂va视频va在线| 欧美福利影院| 欧美视频一区| 国产日韩精品视频一区| 一区二区视频免费完整版观看| 一区二区视频在线观看| 亚洲人成7777| 亚洲特色特黄| 久久狠狠一本精品综合网| 久久久美女艺术照精彩视频福利播放| 欧美一区二区在线播放| 老色鬼精品视频在线观看播放| 免费日韩av电影| 亚洲精品社区| 性色av一区二区三区| 毛片一区二区三区| 欧美亚州韩日在线看免费版国语版| 国产精品一区二区三区四区| 影音先锋日韩精品| 这里是久久伊人| 久久久99免费视频| 亚洲国产欧美在线人成| 亚洲一区二区3| 久久免费黄色| 国产精品乱码一区二区三区 | 欧美三级资源在线| 一区二区三区中文在线观看| 在线亚洲精品| 农夫在线精品视频免费观看| 一区二区三区国产在线观看| 久久久久国产精品www| 欧美午夜理伦三级在线观看| 在线播放亚洲| 欧美一区二区在线播放| 亚洲国产一区二区三区在线播 | 亚洲网在线观看| 欧美88av| 黄色小说综合网站| 亚洲男人第一网站| 亚洲高清免费视频| 欧美在线免费视频| 国产精品久久波多野结衣| 最近中文字幕日韩精品| 久久青青草原一区二区| 亚洲一区免费观看| 欧美视频不卡中文| 99精品国产一区二区青青牛奶| 久久久欧美一区二区| 亚洲一区欧美一区|