hrbust 2163 棋盤取數【最大權獨立集合-------最大流Dinic】

棋盤取數

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 58(18 users) Total Accepted: 13(8 users) Rating:  Special Judge: No

Description

給你一個n*n的格子的棋盤，每個格子裡面有一個非負數。現在從中取出若幹個數，使得任意的兩個數所在的格子沒有公共邊，就是說所取的數所在的2個格子不能相鄰，并且取出的數的和最大。

Input

包括多個測試執行個體，每個測試執行個體包括一個整數n 和n*n個非負數x(n<=20, 0 <= x <= 1000)。

Output

對于每個測試執行個體，輸出可能取得的最大的和。

Sample Input

3 258 83 905 874 941 662 733 415 890

Sample Output

3727

Source

2014暑假集訓練習賽（8月13日）

思路

1、首先，這個題是一個二分圖模型。并且我們知道最大權獨立集=總權-最小割=總權-最大流。

2、那麼我們就在以上基礎建圖。

①我們将點分成兩個集合，i+j為偶數的點我們規定為一個集合，那麼i+j為奇數的點就是另一個集合。

②源點S和i+j為偶數的點都進行建邊，其容量為a【i】【j】，i+j為奇數的點和彙點t都進行建邊，其容量也是a【i】【j】；

③将i+j為偶數的點和周圍四個點進行建邊，其容量為無窮大。

3、求一遍最大流，其解為：總權-最大流、

4、Ford_Fulkerson 、Edmond _Karp都是不可行算法（資料将兩種算法都卡了TLE）。

Ac：

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
int head[100000];
struct EdgeNode
{
    int to;
    int w;
    int next;
}e[1000000];
int div[100000];
int a[25][25];
int fx[4]={0,0,1,-1};
int fy[4]={1,-1,0,0};
int n,cont,ss,tt;
void add(int from,int to,int w)
{
    e[cont].to=to;
    e[cont].w=w;
    e[cont].next=head[from];
    head[from]=cont++;
}
void getmap()
{
    ss=n*n+1;
    tt=ss+1;
    cont=0;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((i+j)%2==0)
            {
                add(ss,(i-1)*n+j,a[i][j]);
                add((i-1)*n+j,ss,0);
            }
            else
            {
                add((i-1)*n+j,tt,a[i][j]);
                add(tt,(i-1)*n+j,0);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if((i+j)%2==1)continue;
            for(int k=0;k<4;k++)
            {
                int x=i+fx[k];
                int y=j+fy[k];
                if(x>=1&&x<=n&&y>=1&&y<=n)
                {
                    add((i-1)*n+j,(x-1)*n+y,INF);
                    add((x-1)*n+y,(i-1)*n+j,0);
                }
            }
        }
    }
}
int makediv()
{
    memset(div,0,sizeof(div));
    div[ss]=1;
    queue<int >s;
    s.push(ss);
    while(!s.empty())
    {
        int u=s.front();
        if(u==tt)return 1;
        s.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            int w=e[i].w;
            if(w&&div[v]==0)
            {
                div[v]=div[u]+1;
                s.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int u,int maxflow,int tt)
{
    if(u==tt)return maxflow;
    int ret=0;
    for(int i=head[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        int w=e[i].w;
        if(w&&div[v]==div[u]+1)
        {
            int f=Dfs(v,min(maxflow-ret,w),tt);
            e[i].w-=f;
            e[i^1].w+=f;
            ret+=f;
            if(ret==maxflow)return ret;
        }
    }
    return ret;
}
int Dinic()
{
    int ans=0;
    while(makediv()==1)
    {
        ans+=Dfs(ss,INF,tt);
    }
    return ans;
}
int main()
{
    while(~scanf("%d",&n))
    {
        int output=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
                output+=a[i][j];
            }
        }
        getmap();
        output-=Dinic();
        printf("%d\n",output);
    }
}