|
|
Posted on 2010-10-05 22:35 成幸毅 阅读(446) 评论(0) 编辑 收藏 引用
最大点权独立集的问题。不解释。
 #include <iostream>
#include <queue>
using namespace std;
const int MAXN = 2000;
const int INF = 0x3fffffff;
int c[MAXN][MAXN];
int d[MAXN];
int num[MAXN];
int pre[MAXN];
int s,t,map[MAXN],mat[MAXN][MAXN],value,map2[MAXN];
  void ini_d(int s,int t)  {
memset(num,0,sizeof(num));
for(int i = 0; i <= t; i++)
d[i] = t + 1;
queue<int> Q;
d[t] = 0;
num[0] = 1;
Q.push(t);
int k;
  while(!Q.empty()) {
k = Q.front();Q.pop();
for(int i = 0; i <= t; i++) {
if(c[i][k] >0 && d[i] > t) {
d[i] = d[k] + 1;
num[d[i]]++;
Q.push(i);
 }
}
}
 }
int findAlowArc(int i) {
int j;
for(j = 0; j <= t;j++)
if(c[i][j] > 0 && d[i] == d[j] + 1) return j;
return -1;
}
int reLable(int i ) {
int j;
int mm = INF;
for(j = 0; j <= t; j++) {
if(c[i][j] > 0) mm = min(mm,d[j] + 1);
}
return mm == INF?t+1:mm;
}
int maxFlow(int s,int t) {
ini_d(s,t);
int flow = 0,i = s,j;
memset(pre,-1,sizeof(pre));
int delta;
while(d[s] <= t) {
j = findAlowArc(i);
if(j >= 0) {
pre[j] = i;
i = j;
if(i == t) {
delta = INF;
for(i = t; i != s; i = pre[i]) delta = min(delta,c[pre[i]][i]);
for(i = t; i != s; i = pre[i]) {
c[pre[i]][i] -= delta,c[i][pre[i]] += delta;
}
flow += delta;
}
}
else {
int x = reLable(i);
num[x]++;
num[d[i]]--;
if(num[d[i]] == 0) return flow;
d[i] = x;
if(i != s) i = pre[i];
}
}
return flow;
}
int m,n;
int main() {
while(scanf("%d%d",&n,&m) != EOF && n && m) {
memset(c,0,sizeof(c));
memset(map,0,sizeof(map));
memset(map2,0,sizeof(map2));
memset(mat,0,sizeof(mat));
s = 0;
int sum = 0;
int tot1 = 0, tot2 = 0;
for(int i = 1; i <= n;i++) {
for(int j = 1; j <= m; j++) {
scanf("%d",&value);
sum += value;
if((i + j)%2 == 0) {
map[++tot1] = value;
mat[i][j] = tot1;
}
else {
map2[++tot2] = value;
mat[i][j] = tot2;
}
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) {
if((i+j)%2 == 0) {
if(i - 1 >= 1)
c[mat[i][j]][mat[i-1][j]+tot1] = INF;
if(i + 1 <= n)
c[mat[i][j]][mat[i+1][j]+tot1] = INF;
if(j - 1 >= 1)
c[mat[i][j]][mat[i][j-1]+tot1] = INF;
if(j + 1 <= m)
c[mat[i][j]][mat[i][j+1]+tot1] = INF;
}
}
t = tot1 + tot2 + 2;
for(int i = 1; i <= tot1; i++)
c[s][i] = map[i];
for(int i = 1; i <= tot2; i++)
c[i+tot1][t] = map2[i];
int ans = maxFlow(s,t);
printf("%d\n",sum - ans);
}
// system("pause");
return 0;
}
|