【BZOJ3714】Kuglarz（PA2014）-最小生成树

测试地址：Kuglarz
做法：本题需要用到最小生成树。
看到上面大家肯定会非常疑惑，这个题目是怎么转化成最小生成树的呢？且听我慢慢道来。
我们尝试找到得到 $A_{i}$ （即第 $i$ 个杯子有没有球）的充要条件，答案显然是存在一些选定的区间的异或值等于 $A_{i}$ 。我们把这个条件转化，注意到，若把区间 $[i, j]$ 转化成无向边 $(i - 1, j)$ ，那么这个条件就相当于能通过选定的边从点 $i - 1$ 走到点 $i$ 。为什么能这样转化？可以把走的过程看成，每走一条边就异或上这条边表示的区间，那么最后肯定就只剩下 $A_{i}$ 了。
那么我们知道能得到 $A_{i}$ 的条件就是点 $i - 1$ 和点 $i$ 连通，那么要找到所有的 $A_{i}$ ，就是让点 $0$ 到点 $N$ 都连通，并且所需代价最小，这显然做一个最小生成树就行了。因为边数很大，不能使用Kruskal算法，要用Prim算法来求。
（啊，终于找到这题了，很久之前我在博客里写过这题的思路，但是没找到原题，现在行了）
以下是本人代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1000000000ll*1000000000ll;
int n;
ll ans=0,g[2010][2010],dis[2010];
bool vis[2010]={0};

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            scanf("%lld",&g[i][j+1]),g[j+1][i]=g[i][j+1];

    vis[1]=1;
    for(int i=2;i<=n+1;i++)
        dis[i]=g[1][i];
    ans=0;
    for(int i=2;i<=n+1;i++)
    {
        ll mn=inf;
        int x;
        for(int j=1;j<=n+1;j++)
            if (!vis[j]&&dis[j]<mn)
            {
                mn=dis[j];
                x=j;
            }
        vis[x]=1;
        ans+=mn;
        for(int j=1;j<=n+1;j++)
            dis[j]=min(dis[j],g[x][j]);
    }
    printf("%lld",ans);

    return 0;
}