  Code
1 //hdu 1569 最大点权独立集
2//一直WA 结果发现又是算法理解错了：来源于amber的最小割模型在信息学竞赛中的应用一文中
3//其中转换步骤为：
4//支撑定理：最大独立集的补集=最小点权覆盖集=最小割
5//在原图点集的基础上增加源s和汇t；将每条二分图（无向图）的边(u,v)替换为有向图G的由u->v的边，容量为INF
6//注意是单向的一条边，而没有v->u 就是因为这里导致了一直wa 。。。太粗心了我！
7//对于二分图两个二分点集合A、B，对A中每个点，连一条容量为wi(A中点vi的点权)的由s到vi的边。对B中每个点
8//连一条由vi到t的，容量为wi的边。然后求解最大流后，转换得到最大独立集
9#include "stdio.h"
10#include "string.h"
11
12#define INF 900000000
13#define M 25010
14#define N 5050
15#define DD 800000000
16
17struct nod
18 {
19 int to;
20 int nxt;
21 int d;
22 };
23
24nod e[M];
25int next[N];
26int en=0;
27int h[N],vh[N];
28int n,augc,m;//augc为增广路容量
29int flow=0;
30int S,H;
31
32void Insert(int fr,int to,int d)
33{
34 e[en].to=to;
35 e[en].d=d;
36 e[en].nxt=next[fr];
37 next[fr]=en;
38 en++;
39 e[en].to=fr;
40 e[en].d=0;
41 e[en].nxt=next[to];
42 next[to]=en;
43 en++;
44}
45
46bool aug(int v)
47{
48 int i,p,augco,minh;
49 minh=n-1;
50 augco=augc;
51 if(v==H)
52  {
53 flow+=augc;
54 return true;
55 }
56 for(i=next[v];i!=-1;i=e[i].nxt)
57 {
58 p=e[i].to;
59 if(e[i].d>0)
60 {
61 if(h[p]+1==h[v])
62 {
63 if(e[i].d<augc)
64 augc=e[i].d;
65 if(aug(p)) break;
66 if(h[S]>=n) return false;//GAP
67 augc=augco;
68 }
69 if(h[p]<minh)
70 minh=h[p];
71 }
72 }
73 if(i==-1)//修改顶标
74 {
75 vh[h[v]]--;
76 if(vh[h[v]]==0)
77 h[S]=n;//GAP
78 h[v]=minh+1;
79 vh[h[v]]++;//GAP
80 return false;
81 }
82 else
83 {
84 e[i].d-=augc;//修改残留
85 e[i^1].d+=augc;
86 return true;
87 }
88}
89int main()
90{
91 int i,j,d,src,des,p,Row,Col,sum;
92 while(scanf("%d %d",&Row,&Col)!=EOF)
93 {
94 en=0;
95 memset(h,0,sizeof(h));
96 memset(vh,0,sizeof(vh));
97 memset(next,-1,sizeof(next));
98 n=Row*Col;
99 src=0;
100 des=n+1;
101 sum=0;
102 for(i=0;i<Row;i++)
103 {
104 for(j=1;j<=Col;j++)
105 {
106 scanf("%d",&d);
107 sum+=d;p=i*Col+j;
108 if((i+j)%2)
109 {
110 Insert(src,p,d);
111 if(j<Col)
112 {
113 Insert(p,p+1,DD);
114 }
115 if(i<Row-1)
116 {
117 Insert(p,p+Col,DD);
118 }
119 if(i>0)
120 Insert(p,p-Col,DD);
121 if(j>1)
122 {
123 Insert(p,p-1,DD);
124 }
125 }
126 else
127 {
128 Insert(p,des,d);
129 }
130 }
131 }
132
133 S=src;
134 H=des;
135 n=n+2;
136 vh[0]=n;
137 flow=0;
138 while(h[S]<n)
139 {
140 augc=INF;
141 aug(S);
142 }
143 printf("%d\n",sum-flow);
144 }
145 return 0;
146}
|
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 24 | 25 | 26 | 27 | 28 | 29 | 30 | | 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)
搜索
最新评论
阅读排行榜
评论排行榜
|
|