原文链接http://www.cnblogs.com/zhouzhendong/p/9010945.html

题目传送门 - Codechef STMINCUT

题意

  在一个有边权的无向图中,我们定义$S$和$T$的最小割为,要使得不存在$S$和$T$之间的路径需要删去的边的最小边权和。 给定$N×N$的二维数组$A$,你可以令数组的任意元素加上一个非负整数(每个元素加上的数可以不同)。加完后,数组$A$应当满足这一条件:存在$N$个节点的图$G$(节点编号为$1$∼$N$),使 得对于任意$i, j (1 ≤ i, j ≤ N)$,$i$和$j$在图$G$中的最小割恰好为$A_{i,j}$。我们定义上述操作的代价为加上的数字之和。请求出最小代价。

  多组数据。

  $T\leq 100,N\leq 1000,\sum N\leq 2000,A_{i,j}\leq 10^9$

题解

  先大力猜一个结论!!(后面填坑)

  最后得到的图是个森林。

  考虑到两点之间的最小割就是他们两个之间的树上路径的最小边权(如果不连通那么显然是$0$)。

  考虑到如果某一条边是某一个连通块中最小的边,那么这条边连通的两个连通块之间的点对之间的最小割显然是该边的权值。

  于是我们考虑从大到小加边。

  由于我们要最小化增量,所以我们取的边权就是输入的矩阵中的数字。

  显然可以$kruskal$来做。

  下面我们分情况讨论:

  如果当前要加入的边所对应的两个连通块

    $\rightarrow$ 不连通:那么,由于当前加入的边比之前加入的都要小,而当前还没有连通的所有点的最小割都不大于当前边权,所以用当前边连接对应的两个连通块中的任意两个点之后,不改变原来连通块内的最小割,并使得两个连通块之间的任意两点最小割大小提升到当前边权值。考虑到如果使该边的权值更大,显然会亏。

    $\rightarrow$ 连通:比如已经存在一条边沟通了两个连通块,并且修改了当前边所连接的两个节点的最小割值,所以当前边已经废了。不管他就可以了。

  然后我们只需要把任意两个节点之间的最小割总和算出来,减掉原来的矩阵数总和即可。

  然后我们考虑(yy)一下为什么森林是最优的(当然不是森林也可能是最优的)。

  开始口胡:

  考虑按照最小割需求从大到小做,在连接两个联通块的时候,如果选择连接的边不止一条边,那么每条边的权会比当前最小割需求平均一些。这样会导致一条路径的最小割不一定是新加入的边——由于之前可能已经加入较小的边了。所以我们需要在这个基础上继续添加边(显然已经亏了)。如果之前没有加入“较小的边”,那么新加入的边连接联通块之后,得到的效果和连一条树边效果相同。

  所以,最终结果为森林虽然不一定是唯一一个最优结果图,但是一定是最优的。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2005;
int T,n,a[N][N],fa[N],size[N];
LL ans,tot;
struct Point{
int x,y;
Point(){}
Point(int _x,int _y){
x=_x,y=_y;
}
}v[N*N];
int getf(int x){
return fa[x]==x?x:fa[x]=getf(fa[x]);
}
bool cmp(Point x,Point y){
return a[x.x][x.y]>a[y.x][y.y];
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
v[(i-1)*n+j]=Point(i,j);
}
sort(v+1,v+n*n+1,cmp);
for (int i=1;i<=n;i++)
fa[i]=i,size[i]=1;
ans=tot=0;
for (int i=1;i<=n*n;i++){
int x=getf(v[i].x),y=getf(v[i].y);
if (x==y)
continue;
ans+=1LL*a[v[i].x][v[i].y]*size[x]*size[y];
size[x]+=size[y],fa[y]=x;
}
ans*=2;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
ans-=a[i][j];
printf("%lld\n",ans);
}
return 0;
}

  

最新文章

  1. 安装cocoapods遇到两大坑-Ruby版本升级和Podfile的配置
  2. Vagrant使用
  3. JDBC基础二
  4. NFC Forum : Frequently Asked Questions (NFC 论坛:FAQ)
  5. Apache / PHP 5.x Remote Code Execution Exploit
  6. Linux中断分层技术
  7. VMware3种网络模式
  8. [Django]models定义choices 字典中的页面显示值
  9. git合并远端分支到本地分支的两种方式
  10. VB6之SendMessage模拟拖放事件
  11. 十九. 想快速开发app,需要找外包吗?
  12. python基本使用事项
  13. docker 下运行 postgresql 的命令
  14. JAVA中的引用
  15. Math.random 随机数方法
  16. &lt;[长期赢利:股票价值投资方法]&gt;读书笔记
  17. python3 unittest框架失败重跑加截图支持python2,python3
  18. HDU - 5406 CRB and Apple (费用流)
  19. BZOJ1484 [HNOI2009]通往城堡之路
  20. Python——通过斐波那契数列来理解生成器

热门文章

  1. MicroPython的开发板
  2. ORACLE透明加密
  3. Winform中的TextBox的小技巧
  4. Confluence 6 Home 和其他重要的目录
  5. Confluence 6 数据库整合的限制
  6. python----常用功能
  7. git bash中的快捷键
  8. 微信小程序 如何获取用户code
  9. JSON数据写入和解析
  10. tomcat和server安装和操作