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

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

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

　　代码如下：

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <vector>
  5 #include <stack>
  6 #include <queue>
  7 using namespace std;
  8 const int N = 1000 + 5;
  9 typedef pair<int, int> pii;
 10 
 11 struct edge
 12 {
 13     int u, v, w;
 14 };
 15 int n, m, k;
 16 unsigned int tot;
 17 vector<edge> G[N];
 18 int dfs_clock, bcc_cnt, dfn[N];
 19 edge S[N*2];
 20 int top;
 21 vector<int> a[N*2];
 22 int ans[2][100000 + 50], sz[2];
 23 void init()
 24 {
 25     memset(dfn, 0, sizeof dfn);
 26     for(int i=1;i<=n;i++) G[i].clear();
 27     dfs_clock = 0;
 28     bcc_cnt = 0;
 29     tot = 0;
 30     top = 0;
 31     memset(ans, 0, sizeof ans);
 32     sz[0] = 1;
 33 }
 34 int test = 0;
 35 void tarjan(int u, int fa)
 36 {
 37     dfn[u] = ++dfs_clock;
 38     for(int i=0;i<G[u].size();i++)
 39     {
 40         edge e = G[u][i];
 41         int v = e.v, w = e.w;
 42         if(v == fa) continue;
 43         if(!dfn[v])
 44         {
 45             S[++top] = e;
 46             tarjan(v, u);
 47             top--;
 48         }
 49         else if(dfn[v] < dfn[u])
 50         {
 51             bcc_cnt++;
 52             a[bcc_cnt].clear();
 53             a[bcc_cnt].push_back(e.w);
 54             int top1 = top;
 55             for(;;)
 56             {
 57                 edge x = S[top1--];
 58                 a[bcc_cnt].push_back(x.w);
 59                 if(x.u == v) break;
 60             }
 61         }
 62     }
 63 }
 64 bool cmp(int x, int y) {return x > y;}
 65 struct node
 66 {
 67     int id, w;
 68     bool operator < (const node & temp) const
 69     {
 70         return w < temp.w;
 71     }
 72 };
 73 void merge(int *pre, int r, vector<int> &v, int *now)
 74 {
 75     priority_queue<node> Q;
 76     for(int i=0;i<v.size();i++) Q.push((node){0, pre[0] + v[i]});
 77     for(int i=0;i<k;i++)
 78     {
 79         sz[(r+1)&1] = i + 1;
 80         node temp = Q.top(); Q.pop();
 81         now[i] = temp.w;
 82         if(temp.id + 1 < sz[r&1]) Q.push((node){temp.id+1, temp.w-pre[temp.id]+pre[temp.id+1]});
 83         if(Q.empty()) break;
 84     }
 85 }
 86 
 87 int main()
 88 {
 89     int kase = 1;
 90     while(scanf("%d%d",&n,&m) == 2)
 91     {
 92         init();
 93         for(int i=1;i<=m;i++)
 94         {
 95             int u, v, w;
 96             scanf("%d%d%d",&u,&v,&w);
 97             G[u].push_back((edge){u, v, w});
 98             G[v].push_back((edge){v, u, w});
 99             tot += w;
100         }
101         scanf("%d",&k);
102         tarjan(1, -1);
103         for(int i=1;i<=bcc_cnt;i++)
104         {
105             sort(a[i].begin(), a[i].end(), cmp);
106             merge(ans[(i-1)&1],i-1,a[i],ans[i&1]);
107         }
108         unsigned int sum = 0;
109         for(int i=0;i<sz[bcc_cnt&1];i++)
110         {
111             sum += (unsigned int)(i+1) * (unsigned int)(tot-ans[bcc_cnt&1][i]);
112         }
113         printf("Case #%d: %u
",kase++,sum);
114     }
115     return 0;
116 }