【学术篇】洛谷1550——打井Watering Hole

题目の传送门：https://www.luogu.org/problem/show?pid=1550

精简版题意（本来就精简了不是么）：n个点，每个点可以选择打井或从别的有水的点引水，求所有点都有水用的最小费用。

这题其实并不是很难。。
令我感到有趣的是这题中一种非常神奇的解题思路。。

首先，如果这个题没有打井的选项，显然是最小生成树
然而我们现在要打井，就不能直接用最小生成树做了。。
殊不知，这题还是一个最小生成树~

这就需要一些小小的、巧妙的办法了。。哦，

新建一个伪节点n+1,向每个点连边，边权是这一点打井的费用！！！

然后我们就可以跑最小生成树了2333

似乎可以证明？

在最小生成树上，抛开我们新建的伪节点不看，剩下的部分一定是一个或多个连通块，而且这些连通块也满足最小生成树的性质，费用是最小的。而这些连通块中，需要有一个打井费用最小的节点来打井，这一点我们跑最小生成树的时候就连到了伪节点上。
显然，对于点i，如果引水费用小于打井，跑最小生成树时就会连到连通块上，表示选择引水，反之则连到伪节点上，表示打井。因为最小生成树上有伪节点存在，从而保证了至少有一个点与其相连，即至少有一个点选择打井。

十分不严谨的证明完了，大家理解就好，不要深究。。

然后就是代码了，明白了原理就非常简单了。。
尽管图非常稠密，然而我还是跑Kruskal，毕竟数据范围只有N<=300，边数也不会超过10W

代码：

#include <cstdio>

#include <algorithm>

using std::sort;

const int MAXV=303;

const int MAXE=MAXV*MAXV+100;

struct edge{

    int from,to,data;

}e[MAXE];

int fa[MAXV],tot,cnt,ans;

int find(int x){

    if(fa[x]!=x) fa[x]=find(fa[x]);

    return fa[x];

}

inline int gnum(){

    int a=0;char c=getchar();bool f=0;

    for(;(c<'0'||c>'9')&&c!='-';c=getchar());

    if(c=='-') c=getchar(),f=1;

    for(;c>='0'&&c<='9';c=getchar()) a=(a<<1)+(a<<3)+c-'0';

    if(f) return ~a+1; return a;

}

bool operator <(const edge &a,const edge &b){

    return a.data<b.data;

}

void build(int x,int y,int z){

    e[++tot].from=x; e[tot].to=y; e[tot].data=z;

}

int main(){

    int n=gnum();

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

        build(i,n+1,gnum()),fa[i]=i;

    fa[n+1]=n+1;

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

        for(int j=1;j<=n;j++)

            build(i,j,gnum());

    sort(e+1,e+tot+1);

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

        if(cnt==n) break;

        int x=find(e[i].from),y=find(e[i].to);

        if(x-y) fa[y]=x,ans+=e[i].data;

    }

    printf("%d",ans);

}

就这样，虽然跑得慢，但是能过嘛= =

你说贪心？留给你自己思索去吧~~