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) ($)

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

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 using PII = pair<int,int>;
 4 const int maxn = 3100;
 5 int head[maxn],uf[maxn],dfn[maxn],low[maxn],clk,tot,ret;
 6 struct arc {
 7     int to,next;
 8     arc(int x = 0,int z = -1) {
 9         to = x;
10         next = z;
11     }
12 } e[1000010];
13 vector<PII>g[maxn];
14 void add(int u,int v) {
15     e[tot] = arc(v,head[u]);
16     head[u] = tot++;
17 }
18 int Find(int x) {
19     if(x != uf[x]) uf[x] = Find(uf[x]);
20     return uf[x];
21 }
22 void tarjan(int u,int fa) {
23     dfn[u] = low[u] = ++clk;
24     bool flag = true;
25     for(int i = head[u]; ~i; i = e[i].next) {
26         if(e[i].to == fa && flag) {
27             flag = false;
28             continue;
29         }
30         if(!dfn[e[i].to]) {
31             tarjan(e[i].to,u);
32             low[u] = min(low[u],low[e[i].to]);
33             if(low[e[i].to] > dfn[u]) ++ret;
34         } else low[u] = min(low[u],dfn[e[i].to]);
35     }
36 }
37 int main() {
38     int kase,n;
39     scanf("%d",&kase);
40     while(kase--) {
41         scanf("%d",&n);
42         for(int i = ret = 0; i < maxn; ++i) {
43             uf[i] = i;
44             g[i].clear();
45         }
46         for(int i = 1,tmp; i < n; ++i) {
47             for(int j = i + 1; j <= n; ++j) {
48                 scanf("%d",&tmp);
49                 g[tmp].push_back(PII(i,j));
50             }
51         }
52         for(int i = 1; i < maxn; ++i) {
53             memset(dfn,0,sizeof dfn);
54             memset(head,-1,sizeof head);
55             tot = 0;
56             for(int j = g[i].size()-1; j >= 0; --j) {
57                 int u = Find(g[i][j].first);
58                 int v = Find(g[i][j].second);
59                 if(u != v) {
60                     add(u,v);
61                     add(v,u);
62                 }
63             }
64             for(int j = 1; j <= n; ++j)
65                 if(!dfn[j]) tarjan(j,-1);
66             for(int j = g[i].size()-1; j >= 0; --j) {
67                 int u = Find(g[i][j].first);
68                 int v = Find(g[i][j].second);
69                 if(u != v) uf[u] = v;
70             }
71         }
72         printf("%d
",ret);
73     }
74     return 0;
75 }

View Code