3714: [PA2014]Kuglarz

链接

思路：

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

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

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

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

代码

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 using namespace std;

 typedef long long LL;

 struct Edge{

     int u,v,w;

     Edge() {}

     Edge(int a,int b,int c) {u=a,v=b,w=c;}

     bool operator < (const Edge &x) const {

         return w < x.w;

     }

 }e[];

 int fa[];

 int tot = ;

 inline int read() {

     int x = ,f = ;char ch=getchar();

     for (; ch<''||ch>''; ch=getchar()) if(ch=='-')f=-;

     for (; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

     return x*f;

 }

 int find(int x) {

     return x==fa[x]?x:find(fa[x]);

 }

 int main () {

     int n = read();

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

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

             e[++tot] = Edge(i,j+,read());

         }

     for (int i=; i<=n+; ++i) fa[i] = i;

     sort(e+,e+tot+);

     int cnt = ;

     LL ans = ;

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

         int u = e[i].u,v = e[i].v,w = e[i].w;

         int fu = find(u),fv = find(v);

         if (fu == fv) continue;

         fa[fu] = fv;

         ans += w;

         cnt ++;

         if (cnt == n) break;

     }

     cout << ans;

     return ;

 }