HDU 6041 I Curse Myself ——（仙人掌图，tarjan，转化）

　　题解见这个博客：http://blog.csdn.net/ME495/article/details/76165039。

　　复杂度不太会算。。这个经典问题的解法需要注意，维护队列里面只有k个元素即可。另外，tarjan对无向图仙人掌图缩点（即只把所有环变成一个点）得注意一下（栈得手写才能实现要求，这是因为在这里割边不能被算进环内，而在有向图中，一个点也算是强连通分量的）。

　　代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <vector>

 #include <stack>

 #include <queue>

 using namespace std;

 const int N =  + ;

 typedef pair<int, int> pii;

 struct edge

 {

     int u, v, w;

 };

 int n, m, k;

 unsigned int tot;

 vector<edge> G[N];

 int dfs_clock, bcc_cnt, dfn[N];

 edge S[N*];

 int top;

 vector<int> a[N*];

 int ans[][ + ], sz[];

 void init()

 {

     memset(dfn, , sizeof dfn);

     for(int i=;i<=n;i++) G[i].clear();

     dfs_clock = ;

     bcc_cnt = ;

     tot = ;

     top = ;

     memset(ans, , sizeof ans);

     sz[] = ;

 }

 int test = ;

 void tarjan(int u, int fa)

 {

     dfn[u] = ++dfs_clock;

     for(int i=;i<G[u].size();i++)

     {

         edge e = G[u][i];

         int v = e.v, w = e.w;

         if(v == fa) continue;

         if(!dfn[v])

         {

             S[++top] = e;

             tarjan(v, u);

             top--;

         }

         else if(dfn[v] < dfn[u])

         {

             bcc_cnt++;

             a[bcc_cnt].clear();

             a[bcc_cnt].push_back(e.w);

             int top1 = top;

             for(;;)

             {

                 edge x = S[top1--];

                 a[bcc_cnt].push_back(x.w);

                 if(x.u == v) break;

             }

         }

     }

 }

 bool cmp(int x, int y) {return x > y;}

 struct node

 {

     int id, w;

     bool operator < (const node & temp) const

     {

         return w < temp.w;

     }

 };

 void merge(int *pre, int r, vector<int> &v, int *now)

 {

     priority_queue<node> Q;

     for(int i=;i<v.size();i++) Q.push((node){, pre[] + v[i]});

     for(int i=;i<k;i++)

     {

         sz[(r+)&] = i + ;

         node temp = Q.top(); Q.pop();

         now[i] = temp.w;

         if(temp.id +  < sz[r&]) Q.push((node){temp.id+, temp.w-pre[temp.id]+pre[temp.id+]});

         if(Q.empty()) break;

     }

 }

 int main()

 {

     int kase = ;

     while(scanf("%d%d",&n,&m) == )

     {

         init();

         for(int i=;i<=m;i++)

         {

             int u, v, w;

             scanf("%d%d%d",&u,&v,&w);

             G[u].push_back((edge){u, v, w});

             G[v].push_back((edge){v, u, w});

             tot += w;

         }

         scanf("%d",&k);

         tarjan(, -);

         for(int i=;i<=bcc_cnt;i++)

         {

             sort(a[i].begin(), a[i].end(), cmp);

             merge(ans[(i-)&],i-,a[i],ans[i&]);

         }

         unsigned int sum = ;

         for(int i=;i<sz[bcc_cnt&];i++)

         {

             sum += (unsigned int)(i+) * (unsigned int)(tot-ans[bcc_cnt&][i]);

         }

         printf("Case #%d: %u\n",kase++,sum);

     }

     return ;

 }