3714: [PA2014]Kuglarz

思路：

　　好题。对于每个点都需要确定它的值，那么一个点可以直接询问[i,i]来确定，或者已经知道了[i,j]和[i+1,j]推出来。

　　但是可能产生冲突，所以要增加一些限制。比如选了[1,1]和[2,2]就不能再选[1,2]了。

　　还有一个结论：答案一定是询问n次。这个在纸上画一下吧。

　　对于这些限制，刚好可以用生成树来做（树是不允许有环的），然后发现如果直接建图是不可以做的，需要将点化为边，在n+1个点中选n条边。

代码

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<iostream>
 4 
 5 using namespace std;
 6 typedef long long LL;
 7 
 8 struct Edge{
 9     int u,v,w;
10     Edge() {} 
11     Edge(int a,int b,int c) {u=a,v=b,w=c;}
12     bool operator < (const Edge &x) const {
13         return w < x.w;
14     }
15 }e[5000100];
16 int fa[10010];
17 int tot = 0;
18 
19 inline int read() {
20     int x = 0,f = 1;char ch=getchar();
21     for (; ch<'0'||ch>'9'; ch=getchar()) if(ch=='-')f=-1;
22     for (; ch>='0'&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
23     return x*f;
24 }
25 
26 int find(int x) {
27     return x==fa[x]?x:find(fa[x]);
28 }
29 int main () {
30     int n = read();
31     for (int i=1; i<=n; ++i) 
32         for (int j=i; j<=n; ++j) {
33             e[++tot] = Edge(i,j+1,read());
34         }
35     for (int i=1; i<=n+1; ++i) fa[i] = i;
36     sort(e+1,e+tot+1);
37     int cnt = 0;
38     LL ans = 0;    
39     for (int i=1; i<=tot; ++i) {
40         int u = e[i].u,v = e[i].v,w = e[i].w;
41         int fu = find(u),fv = find(v);
42         if (fu == fv) continue;
43         fa[fu] = fv;
44         ans += w;
45         cnt ++;
46         if (cnt == n) break;
47     }
48     cout << ans;
49     return 0;
50 }