hdu1565方格取数(一) 最大流之 最大点权独立集

hdu1565方格取数(1) 最大流之 最大点权独立集

//给一个n*n的矩阵，问从这个矩阵中若干数，这些数不相邻
//问这些数的最大值为多少
//1. 最小点权覆盖集=最小割=最大流
//2. 最大点权独立集=总权-最小点权覆盖集
//将(i+j)%2 == 1分为x集，将(i+j)%2==0分为y集
//对x集向y集相邻的边引入权值为inf的边
//源点向x集引入权值为该点权值的边 ， 从y集向汇点引入权值为该点权值的边
//那么答案是其最大点权独立集
#include<cstdio>
#include<cstring>
#include<queue>
#include<iostream>
using namespace std ;
const int maxn = 1010 ;
const int inf = 0x3f3f3f3f ;
int map[30][30] ;
int dx[4] = {0 , 1 , 0 , -1};
int dy[4] = {1 , 0 , -1 , 0};
int st = 0 , en = 1001 ;
struct Edge
{
    int v ;int w ;
    int next ;
}edge[maxn*maxn] ;
int  head[maxn] ;
int nedge ;int dis[maxn] ;
void addedge(int u , int v ,int w)
{
    edge[nedge].v = v ;
    edge[nedge].w = w ;
    edge[nedge].next = head[u] ;
    head[u] = nedge++ ;
    edge[nedge].v = u ;
    edge[nedge].w = 0 ;
    edge[nedge].next = head[v] ;
    head[v] = nedge++ ;
}
bool bfs()
{
    memset(dis , -1 , sizeof(dis)) ;
    dis[st] = 0;
    queue<int> que ;
    que.push(st) ;
    while(que.size())
    {
        int u = que.front() ;que.pop() ;
        for(int i = head[u];i != -1 ;i = edge[i].next)
        {
            int v = edge[i].v ;
            if(dis[v] < 0 && edge[i].w > 0)
            {
                dis[v] = dis[u] + 1 ;
                que.push(v) ;
            }
        }
    }
    if(dis[en] > 0)return true ;
    return false ;
}
int dfs(int u , int mx)
{
    if(u == en)
    return mx ;
    int ans = 0 ;int a ;
    for(int i = head[u]; i != -1 ;i = edge[i].next)
    {
        int v = edge[i].v ;
        if(dis[v] == dis[u] + 1 && edge[i].w > 0 && (a = dfs(v , min(mx , edge[i].w))))
        {
            mx -= a ;
            ans += a ;
            edge[i].w -= a ;
            edge[i^1].w += a ;
            if(!mx)break ;
        }
    }
    if(!ans)dis[u] = -1 ;
    return ans ;
}
int main()
{
    //freopen("in.txt" , "r" , stdin) ;
    int n ;
    while(~scanf("%d" , &n))
    {
        memset(head , -1 , sizeof(head)) ;
        nedge = 0 ;
        int sum = 0 ;
        for(int i = 1;i <= n;i++)
           for(int j = 1;j <= n;j++)
             scanf("%d" , &map[i][j]) ,sum += map[i][j] ;
        for(int i = 1;i <= n;i++)
           for(int j = 1;j <= n;j++)
           {
               int t = (i + j)%2 ;
               if(t)
               {
                   for(int k = 0;k < 4;k++)
                   {
                       int x = dx[k] + i ;
                       int y = dy[k] + j ;
                       if(x < 1 || x > n || y < 1 || y > n || (x+y)%2)
                       continue ;
                       addedge((i-1)*n+j , (x-1)*n+y , inf);
                   }
                   addedge(st , (i-1)*n+j , map[i][j]) ;
               }
               else addedge((i-1)*n+j , en , map[i][j]) ;
           }
        int ans = 0 ;
        int res ;
        while(bfs())
            while(res = dfs(st , inf))
            ans += res ;
        cout<<sum - ans<<endl;
    }
    return 0 ;
}