BZOJ 1601 [Usaco2008 Oct]灌水 MST

题意:链接方法: MST解析:前两天刚写完不知道怎么回事没有发上去， 所以只好重写。这题坑了我挺长时间。第一发思路是DP，后来发现这个W数组不单调，所以想排序一下后DP，但是无卵用，因为还有边权，w极小边权可能极大，所以这个思路很快就D掉了。第二发思路是网络流，暂且不谈这个复杂度的问题，我们来考虑中国式网络流！怎么流呢，拆点，每个点拆两个，然后连流量为1的边，然后就不对了，，流量是1的话，他之后连的点可能有很多，但是被限制成1了，即便我们给他INF的流量，那么就会重新计算好多次W，所以也不对，那如果我们赋INF跑完后O(n)删除一下不应该有的流量呢？也不对，因为删除后不能保证是最小费用了，所以这发思路也被D。第三发，实在没有办法，重新审视一下题目，每个点有几种情况呢？两种，第一种是自己给自己灌水，第二种是别人给他灌。别人给他灌的情况可以直接连边，但是自己怎么办呢？有了网络流的思想就不怕了，建立一个源点，向每个点连一条权值为w[i]的边，这样的话再怎么想呢？我们要取所有的点，包括源点，还要费用最小，这不就是MST么，正确性显然啊，所以MST解就好了。另外这题n^2的边，如果上kruscal的话O(eloge)是可过的，但是会慢一点，反正能过就行。prim的优越性在这种稠密图中就体现啦。然而我写的是kruscal.代码:;int n;int fa[N];struct node{int from,to,val;}l[N*N*2];int find(int x){if(fa[x]!=x)return fa[x]=find(fa[x]);return x;}int cmp(node a,node b){return a.val<b.val;}int tot;int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++){int x;scanf(“%d”,&x);l[++tot].from=1,l[tot].to=i+1,l[tot].val=x;fa[i]=i;}fa[n+1]=n+1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int x;scanf(“%d”,&x);if(i==j)continue;l[++tot].from=i+1,l[tot].to=j+1,l[tot].val=x;}}sort(l+1,l+tot+1,cmp);int ans=0,cntchoose=0;for(int i=1;i<=tot;i++){int x=l[i].from,y=l[i].to;int fx=find(x),fy=find(y);if(fx!=fy){fa[fx]=fy;ans+=l[i].val;cntchoose++;if(cntchoose==n)break;}}printf(“%d\n”,ans);}

只有经历过地狱般的折磨，才有征服天堂的力量，只有流过血的手指，才能弹出世间的绝唱。