方格取数(1)
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7717 Accepted Submission(s): 2911
Problem Description
给你一个n*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
Input
包括多个测试实例，每个测试实例包括一个整数n 和n*n个非负数(n<=20)
Output
对于每个测试实例，输出可能取得的最大的和
Sample Input
3
75 15 21
75 15 28
34 70 5
75 15 21
75 15 28
34 70 5
Sample Output
188
Author
ailyanlu
最小点权覆盖集＋最大点权独立集 ＝ 图的总权值
最小点权覆盖集=最大流=最小割
覆盖集、独立集是图论中的相关概念.
而这两个概念在二分图中不是NP问题，所以要把这个图转化为二分图求解。
先建立一个超级源点和一个超级汇点，然后将(x+y)为偶数（或者奇数）的点与超级源点连接，将(x+y)为奇数（或者偶数）的点与超级汇点连接，二分图两边的点相连的权值都记为正无穷，然后对此图求最小割。然后 最大点权独立集 = 总权值 - 最小点权覆盖集
#include <iostream>
#include <queue>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int N = ;
const int INF = ;
struct Edge{
int v,w,next;
}edge[N*N];
int head[N];
int level[N];
int mp[N][N];
int n;
void addEdge(int u,int v,int w,int &k){
edge[k].v = v,edge[k].w=w,edge[k].next=head[u],head[u]=k++;
edge[k].v = u,edge[k].w=,edge[k].next=head[v],head[v]=k++;
}
int BFS(int src,int des){
queue<int >q;
memset(level,,sizeof(level));
level[src]=;
q.push(src);
while(!q.empty()){
int u = q.front();
q.pop();
if(u==des) return ;
for(int k = head[u];k!=-;k=edge[k].next){
int v = edge[k].v,w=edge[k].w;
if(level[v]==&&w!=){
level[v]=level[u]+;
q.push(v);
}
}
}
return -;
}
int dfs(int u,int des,int increaseRoad){
if(u==des) return increaseRoad;
int ret=;
for(int k=head[u];k!=-;k=edge[k].next){
int v = edge[k].v,w=edge[k].w;
if(level[v]==level[u]+&&w!=){
int MIN = min(increaseRoad-ret,w);
w = dfs(v,des,MIN);
edge[k].w -=w;
edge[k^].w+=w;
ret+=w;
if(ret==increaseRoad) return ret;
}
}
return ret;
}
int Dinic(int src,int des){
int ans = ;
while(BFS(src,des)!=-) ans+=dfs(src,des,INF);
return ans;
}
int P(int x,int y){
return (x-)*n+y;
}
int dir[][]={,,-,,,,,-};
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(head,-,sizeof(head));
int tot = ;
int src = ,des = n*n+;
int sum = ;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&mp[i][j]);
sum+=mp[i][j];
if((i+j)%==){
addEdge(src,P(i,j),mp[i][j],tot);
}else{
addEdge(P(i,j),des,mp[i][j],tot);
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
for(int k=;k<=;k++){
int x = i+dir[k][];
int y = j+dir[k][];
if(x<||x>n||y<||y>n) continue;
if((i+j)%==){
addEdge(P(i,j),P(x,y),INF,tot);
}
}
}
}
printf("%d\n",sum-Dinic(,n*n+));
}
return ;
}
hdu 1569
#include <iostream>
#include <queue>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int N = ;
const int INF = ;
struct Edge{
int v,w,next;
}edge[N*N];
int head[N];
int level[N];
int mp[][];
int n,m;
void addEdge(int u,int v,int w,int &k){
edge[k].v = v,edge[k].w=w,edge[k].next=head[u],head[u]=k++;
edge[k].v = u,edge[k].w=,edge[k].next=head[v],head[v]=k++;
}
int BFS(int src,int des){
queue<int >q;
memset(level,,sizeof(level));
level[src]=;
q.push(src);
while(!q.empty()){
int u = q.front();
q.pop();
if(u==des) return ;
for(int k = head[u];k!=-;k=edge[k].next){
int v = edge[k].v,w=edge[k].w;
if(level[v]==&&w!=){
level[v]=level[u]+;
q.push(v);
}
}
}
return -;
}
int dfs(int u,int des,int increaseRoad){
if(u==des) return increaseRoad;
int ret=;
for(int k=head[u];k!=-;k=edge[k].next){
int v = edge[k].v,w=edge[k].w;
if(level[v]==level[u]+&&w!=){
int MIN = min(increaseRoad-ret,w);
w = dfs(v,des,MIN);
edge[k].w -=w;
edge[k^].w+=w;
ret+=w;
if(ret==increaseRoad) return ret;
}
}
return ret;
}
int Dinic(int src,int des){
int ans = ;
while(BFS(src,des)!=-) ans+=dfs(src,des,INF);
return ans;
}
int P(int x,int y){
return (x-)*m+y;
}
int dir[][]={,,-,,,,,-};
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(head,-,sizeof(head));
int tot = ;
int src = ,des = n*m+;
int sum = ;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
scanf("%d",&mp[i][j]);
sum+=mp[i][j];
if((i+j)%==){
addEdge(src,P(i,j),mp[i][j],tot);
}else{
addEdge(P(i,j),des,mp[i][j],tot);
}
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
for(int k=;k<=;k++){
int x = i+dir[k][];
int y = j+dir[k][];
if(x<||x>n||y<||y>m) continue;
if((i+j)%==){
addEdge(P(i,j),P(x,y),INF,tot);
}
}
}
}
printf("%d\n",sum-Dinic(,n*m+));
}
return ;
}