|
Posted on 2010-10-05 22:35 成幸毅 阅读(441) 评论(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; }
|