HDU 5483 Nux Walpurgis

Nux Walpurgis

Time Limit: 8000ms

Memory Limit: 131072KB

This problem will be judged on HDU. Original ID: 5483
64-bit integer IO format: %I64d Java class name: Main

Given a weighted undirected graph, how many edges must be on the minimum spanning tree of this graph?

Input

The first line of the input is a integer T, meaning that there are T test cases.

Every test cases begin with a integer n ,which is the number of vertexes of this graph.

Then n−1 lines follow, the ith line contain n−i integers, the jth number w in this line represents the weight between vertex i and vertex i+j.

1≤T≤20.

1≤n,w≤3,000.

Output

For every test case output the number of edges must be on the minimum spanning tree of this graph.

Sample Input

Sample Output

0

1

Source

BestCoder Round #57 (div.1) ($)

解题：题目还是挺难想的，求图的最小生成树的必要边的数量，学习的是某位大神的解法

 #include <bits/stdc++.h>

 using namespace std;

 using PII = pair<int,int>;

 const int maxn = ;

 int head[maxn],uf[maxn],dfn[maxn],low[maxn],clk,tot,ret;

 struct arc {

     int to,next;

     arc(int x = ,int z = -) {

         to = x;

         next = z;

     }

 } e[];

 vector<PII>g[maxn];

 void add(int u,int v) {

     e[tot] = arc(v,head[u]);

     head[u] = tot++;

 }

 int Find(int x) {

     if(x != uf[x]) uf[x] = Find(uf[x]);

     return uf[x];

 }

 void tarjan(int u,int fa) {

     dfn[u] = low[u] = ++clk;

     bool flag = true;

     for(int i = head[u]; ~i; i = e[i].next) {

         if(e[i].to == fa && flag) {

             flag = false;

             continue;

         }

         if(!dfn[e[i].to]) {

             tarjan(e[i].to,u);

             low[u] = min(low[u],low[e[i].to]);

             if(low[e[i].to] > dfn[u]) ++ret;

         } else low[u] = min(low[u],dfn[e[i].to]);

     }

 }

 int main() {

     int kase,n;

     scanf("%d",&kase);

     while(kase--) {

         scanf("%d",&n);

         for(int i = ret = ; i < maxn; ++i) {

             uf[i] = i;

             g[i].clear();

         }

         for(int i = ,tmp; i < n; ++i) {

             for(int j = i + ; j <= n; ++j) {

                 scanf("%d",&tmp);

                 g[tmp].push_back(PII(i,j));

             }

         }

         for(int i = ; i < maxn; ++i) {

             memset(dfn,,sizeof dfn);

             memset(head,-,sizeof head);

             tot = ;

             for(int j = g[i].size()-; j >= ; --j) {

                 int u = Find(g[i][j].first);

                 int v = Find(g[i][j].second);

                 if(u != v) {

                     add(u,v);

                     add(v,u);

                 }

             }

             for(int j = ; j <= n; ++j)

                 if(!dfn[j]) tarjan(j,-);

             for(int j = g[i].size()-; j >= ; --j) {

                 int u = Find(g[i][j].first);

                 int v = Find(g[i][j].second);

                 if(u != v) uf[u] = v;

             }

         }

         printf("%d\n",ret);

     }

     return ;

 }

巴特西