无向图最小点割集,确定起点S,终点T。每个点都有自己的点权值vi,求最小点权和的割点集,使得S无法到达T。 解法:将每个点拆分为两个点v和v',之间的权值为vi,将原图中的每条边赋权值为INF(无穷大),然后使用最大流算法,求从S到T的最大流,即对应了最小割,其中割边集连接的点形成的点集就是最小点割集。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) Code 1 #include "stdio.h" 2 #include "string.h" 3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 4 #define INF 700000000 5 #define N 500 6 #define DD 20000 7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 8 int c[N][N];//邻接矩阵 9 int h[N],vh[N]; 10 int n,augc,m;//augc为增广路容量 11 int flow=0; 12 int S,H; 13![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 14 bool aug(int v) 15![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 16 int i,augco,minh; 17 minh=n; 18 augco=augc; 19 if(v==H) 20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 21 flow+=augc; 22 return true; 23 } 24 for(i=1;i<=n;i++) 25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 26 if(c[v][i]>0) 27![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 28 if(h[i]+1==h[v]) 29![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 30 if(c[v][i]<augc) 31 augc=c[v][i]; 32 if(aug(i)) break; 33 if(h[S]>=n) return false;//GAP 34 augc=augco; 35 } 36 if(h[i]<minh) 37 minh=h[i]; 38 } 39 } 40 if(i>n)//修改顶标 41![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 42 vh[h[v]]--; 43 if(vh[h[v]]==0) h[S]=n;//GAP 44 h[v]=minh+1; 45 vh[h[v]]++;//GAP 46 return false; 47 } 48 else 49![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 50 c[v][i]-=augc;//修改残留 51 c[i][v]+=augc; 52 return true; 53 } 54 } 55 int main() 56![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 57 int i,T,tmp,fr,to; 58 scanf("%d",&T); 59 while(T--) 60![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 61 scanf("%d %d %d %d",&n,&m,&S,&H); 62 memset(c,0,sizeof(c)); 63 memset(h,0,sizeof(h)); 64 memset(vh,0,sizeof(vh)); 65 for(i=1;i<=n;i++) 66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 67 scanf("%d",&tmp); 68 c[i][i+n]=tmp; 69 } 70 for(i=0;i<m;i++) 71![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 72 scanf("%d %d",&fr,&to); 73 c[fr+n][to]=DD; 74 c[to+n][fr]=DD; 75 } 76 S=S+n; 77 n=2*n; 78 vh[0]=n; 79 flow=0; 80 while(h[S]<n) 81![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 82 augc=INF; 83 aug(S); 84 } 85 printf("%d\n",flow); 86 } 87 return 0; 88 }
|
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 1 | 2 | 3 | 4 | 5 |
|
导航
统计
常用链接
留言簿
随笔分类(1)
随笔档案(2)
文章分类(15)
文章档案(7)
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|