ネットワーク・フローの最小ポイント権オーバーライドと最大ポイント権独立セット

ネットワーク・フローの最小ポイント権最大ポイント権独立セットを上書き
二分図の最小点オーバーライドと最大独立セットは、最大マッチング解に変換できます.これに基づいて,各点に非負の重み値を与えると,この2つの問題は,二分図最小点重みオーバーライドと二分図最大点重み独立セットに変換される.
 
二分図最小点重みオーバーライド
xまたはyのセットからいくつかの点を選択し、これらの点がすべてのエッジを上書きし、選択された点の重み値ができるだけ小さくなります.
モデリング:
元の二分図のエッジ(u,v)をINF容量の有向エッジ(u,v)に置き換え、ソースポイントsとシンクポイントtを設定し、sとx集合のポイントを接続し、容量はそのポイントの重み値である.y中の点をtに接続し、容量はその点の重み値である.新しい図の上で最大の流れを求めて、最大の流量はつまり最小の点の重みのカバーする重みの値とです.
 
二分図最大ポイント独立セット
重み値と最大のポイントセットが二分図に表示され、両者の間にエッジがないようになります.実はそれは最小点権がカバーする対偶問題です.答え=総重み-最小点オーバーライドセット.具体的な証明は胡波濤の論文を参考にする.
 
例:HDU 1569
タイトル:m*nの碁盤で、各格子には重み値があり、そこからいくつかの数を取り出し、任意の2つの数が存在する格子に共通のエッジがなく、取り出された数と最大になる.この最大の値を求めます.
解:
格子を二分図に染色することは,明らかに二分図の最大点権独立セットを求めることである.問題を二分図最小点重みオーバーライドに変換して解き,最終結果=総重みと−最大ストリームである.
 

/*
       ：
           ，       =   -       
      ：
    s t，s    i，   i    ； j   t，   j   ；          INF，            。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int maxv = 2600;
const int maxe = 1000000;
int n,m;
int g[55][55];
struct Edge
{
    int v;
    int next;
    int flow;
};
Edge e[maxe];
int head[maxv],edgeNum;
int now[maxv],d[maxv],vh[maxv],pre[maxv],preh[maxv];
int start,end;

void addEdge(int a,int b,int c)
{
    e[edgeNum].v = b;
    e[edgeNum].flow = c;
    e[edgeNum].next = head[a];
    head[a] = edgeNum++;
    e[edgeNum].v = a;
    e[edgeNum].flow = 0;
    e[edgeNum].next = head[b];
    head[b] = edgeNum++;
}

void Init()
{
    edgeNum = 0;
    memset(head,-1,sizeof(head));
    memset(d,0,sizeof(d));
}

int sap(int s,int t,int n)       //  ，  ，    
{
    int i,x,y;
    int f,ans = 0;
    for(i = 0; i < n; i++)
        now[i] = head[i];
    vh[0] = n;
    x = s;
    while(d[s] < n)
    {
        for(i = now[x]; i != -1; i = e[i].next)
            if(e[i].flow > 0 && d[y=e[i].v] + 1 == d[x])
                break;
            if(i != -1)
            {
                now[x] = preh[y] = i;
                pre[y] = x;
                if((x=y) == t)
                {
                    for(f = INF,i=t; i != s; i = pre[i])
                        if(e[preh[i]].flow < f)
                            f = e[preh[i]].flow;
                    ans += f;
                    do
                    {
                        e[preh[x]].flow -= f;
                        e[preh[x]^1].flow += f;
                        x = pre[x];
                    }while(x!=s);
                }
            }
            else
            {
                if(!--vh[d[x]])
                    break;
                d[x] = n;
                for(i=now[x]=head[x]; i != -1; i = e[i].next)
                {
                    if(e[i].flow > 0 && d[x] > d[e[i].v] + 1)
                    {
                        now[x] = i;
                        d[x] = d[e[i].v] + 1;
                    }
                }
                ++vh[d[x]];
                if(x != s)
                    x = pre[x];
            }
    }
    return ans;
}


void build()
{
    int i,j;
    for(i = 1; i <= m; i++)
    {
        for(j = 1; j <= n; j++)
        {
            int t = (i-1)*n+j;
            if((i+j)%2)
            {
                addEdge(start,t,g[i][j]);
                if(i>1)
                    addEdge(t,t-n,INF);
                if(i<m)
                    addEdge(t,t+n,INF);
                if(j>1)
                    addEdge(t,t-1,INF);
                if(j<n)
                    addEdge(t,t+1,INF);
            }
            else
                addEdge(t,end,g[i][j]);
        }
    }
}

int main()
{
    int i,j;
    int result;
    while(scanf("%d %d",&m,&n) != EOF)
    {
        result = 0;
        Init();
        for(i = 1; i <= m; i++)
        {
            for(j = 1; j <= n; j++)
            {
                scanf("%d",&g[i][j]);
                result += g[i][j];
            }
        }
        start = 0;
        end = n*m + 1;
        build();
        printf("%d
",result-sap(start,end,end+1));
    }
    return 0;
}