题解 P1550 【[USACO08OCT]打井Watering Hole】

· · 题解

本题看似很难，实际上思路非常简单——如果你想通了。

首先有一个问题：图中有几个点？大部分的人会回答n个点。错了，有n+1个。

多出来的那个点在哪？关键在于你要理解每一个决策的意义。实际上，多出来的那个点是地下的FarmerJohn山泉天然矿泉水。当我们打井时，我们实际上是在往地下连边。理解了这一点，代码就没有任何难度了。

构图时，我们只需多加一个点，对于每个点i，我们连边i→n+1，边权为w_i。然后直接跑最小生成树就没了。就没了。

代码：

#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++优先队列是从大到小排的，所以如果你想排序，一定记住把小于号定义里的运算反过来！一定！我刚才被这个坑了半天！