题解 P1550 【[USACO08OCT]打井Watering Hole】
Mr_QwQ
2017-08-30 19:27:24
本题看似很难，实际上思路非常简单——如果你想通了。
首先有一个问题：图中有几个点？大部分的人会回答n个点。错了，有n+1个。
多出来的那个点在哪？关键在于你要理解每一个决策的意义。实际上，多出来的那个点是地下的~~FarmerJohn山泉~~天然矿泉水。当我们打井时，我们实际上是在往地下连边。理解了这一点，代码就没有任何难度了。
构图时，我们只需多加一个点，对于每个点i，我们连边i→n+1，边权为w\_i。然后直接跑最小生成树就没了。就没了。
代码：
```cpp
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct edge{
int from,to,len;
const bool operator < (edge b) const{
return this->len>b.len;
}
}e[100000];
priority_queue <edge> que;
int n,a[302][302],w[301],fa[302],ans;
int find(int x)
{
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
int mst()
{
while(!que.empty()){
edge p=que.top();
if(find(p.from)!=find(p.to))
{
fa[fa[p.to]]=fa[p.from];
ans+=p.len;
}
que.pop();
}
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
if(i!=j)que.push((edge){i,j,a[i][j]});
}
}
n++;
for(int i=1;i<n;i++){
que.push((edge){i,n,w[i]});
que.push((edge){n,i,w[i]});
}
for(int i=1;i<=n;i++)fa[i]=i;
printf("%d",mst());
return 0;
}
```
最后提醒一下用C++STL用惯了的同学：注意C++优先队列是从大到小排的，所以如果你想排序，一定记住把小于号定义里的运算反过来！一定！我刚才被这个坑了半天！