无向图最小点割集，确定起点S，终点T。每个点都有自己的点权值vi，求最小点权和的割点集，使得S无法到达T。
解法：将每个点拆分为两个点v和v'，之间的权值为vi，将原图中的每条边赋权值为INF（无穷大），然后使用最大流算法，求从S到T的最大流，即对应了最小割，其中割边集连接的点形成的点集就是最小点割集。
  Code
1 #include "stdio.h"
2#include "string.h"
3
4#define INF 700000000
5#define N 500
6#define DD 20000
7
8int c[N][N];//邻接矩阵
9int h[N],vh[N];
10int n,augc,m;//augc为增广路容量
11int flow=0;
12int S,H;
13
14bool aug(int v)
15 {
16 int i,augco,minh;
17 minh=n;
18 augco=augc;
19 if(v==H)
20  {
21 flow+=augc;
22 return true;
23 }
24 for(i=1;i<=n;i++)
25 {
26 if(c[v][i]>0)
27 {
28 if(h[i]+1==h[v])
29 {
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 {
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 {
50 c[v][i]-=augc;//修改残留
51 c[i][v]+=augc;
52 return true;
53 }
54 }
55int main()
56{
57 int i,T,tmp,fr,to;
58 scanf("%d",&T);
59 while(T--)
60 {
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 {
67 scanf("%d",&tmp);
68 c[i][i+n]=tmp;
69 }
70 for(i=0;i<m;i++)
71 {
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 {
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 | 31 | 1 | 2 | 3 | 4 |
|
导航
统计
常用链接
留言簿
随笔分类(1)
随笔档案(2)
文章分类(15)
文章档案(7)
搜索
最新评论
阅读排行榜
评论排行榜
|
|