关于prim,其实我今天才学...
prim其实就是最小生成树的一种算法，严格每次的找最小边连到树上。看书上的代码看不懂，于是就自己大胆用堆优化写prim。
搞了很长时间，经过不写努力，还是搞出来了。
代码如下:
inline void prim() {priority_queue<pair<int,int> >q;q.push(make_pair(0,m));while(ans<m){int y=q.top().second;int v=-q.top().first;q.pop();if(vis[y]!=1){minn+=v;ans++;vis[y]=1;for(int i=link[y];i;i=a[i].next){int y1=a[i].y;int v1=a[i].v;q.push(make_pair(-v1,y1));}}} }
有点简陋，但个人还是觉得比较理解，也就是每次加进去一个点，把这个点能连到的点与边权加进队列。之后取出最小的边，判断是否在树里，直到最后所有的点都在树里，prim结束。最小生成树也就完成了。
不说了，来看一道"裸题"：
猛看这道题以为就是练格式的，之后就发现不对了。他要保证的是每个地点有水即不一定要连成一个树，还可以在连起来的代价大于打井的代价时选择打井。连起来的大家都会，不就是连个最小生成树嘛，但是加上打井就有疑问，怎样处理好打井与用管道连起来的关系就是这道题的难点所在。
大家可以这样想：打井之后就不在树里，那我们最小生成树就无法完成。这时怎样将打井和树联系起来就是要思考的问题了。既然打井之后不在树里，哪我们为什么不能把它加进树里，即一个打井费用就是一个边，一共有n打井费用，即n条边，那就可以再加一个点，使其他点到这个点的距离就是那个点的打井费用，这样一共（n+1）个点跑最短路，与n所连的点就是打井的点，最小树也就完成了。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
int n,tot,minn,link[100000],m,ans,vis[100000];
struct bian
{int y,v,next;
};
bian a[1000000];
inline int read()
{int x=0,ff=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') ff=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*ff;
}
inline void add(int x,int y,int v)
{a[++tot].y=y;a[tot].v=v;a[tot].next=link[x];link[x]=tot;
}
inline void prim()
{priority_queue<pair<int,int> >q;q.push(make_pair(0,m));while(ans<m){int y=q.top().second;int v=-q.top().first;q.pop();if(vis[y]!=1){minn+=v;ans++;vis[y]=1;for(int i=link[y];i;i=a[i].next){int y1=a[i].y;int v1=a[i].v;q.push(make_pair(-v1,y1));}}}
}
int main()
{//freopen("1.in","r",stdin);n=read();m=n+1;for(int i=1;i<=n;i++){int v=read();add(m,i,v);add(i,m,v);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int v=read();if(i!=j) add(i,j,v);}}prim();cout<<minn<<endl;return 0;
}
好了，就到这吧！
