最小割与最短路的转换(S-T平面)

    考虑如下问题：

    一个牧场由R*C个点组成。牧场内有若干条运输通道，通道流量上限是Ci，连接水平或者垂直相邻的的点。(1,1)内有很多干草，Farmer John希望将干草运送到点(R,C)。问最大流量是多少。1<R,C<=200。

    一种直观的解法：

    将每个站点看成点，相邻的点之间有边，流量上限为Ci。将(1,1)作为源，(R,C)作为汇，求最大流即可。

    是否可行？

    上述解法，点数最多为40000，边数最大为80000。用最大流sap求解复杂度为(n*n*m)，显然不合理。

    分析：

    题目给出的是一个平面图，并且s和t都在图中无边界面的边界上。在这里，我们称之为S-T平面图。同时利用对偶图(面f-->点f*，边属于两个面f1、f2，有点(f1*,f2*))和原图的关系，转化为最短路径求解。

    具体步骤：

    首先连一条边(s,t)，它将无边界面分解为2个面。求该图的对偶图G*，设无边界面为点t*，附加面为点s*。删去边(s*,t*)。这样，s*到t*的任意一条路径就对应了原图的一个割，显然，最短路径即为最小割。

    例：HDU3870

    题意：裸体。给一个n*n的格子，求从(1,1)到(n,n)的最大流。

    解：同上。

 

/*
S-T平面图最小割转最短路径
建模：
1.在原图中添加一条从s到t的边，得到一个附加面，变为图G。
2.求图G的对偶图G*：
    G的面i-->G*的点i，G的一条边若属于两个平面i,j，G*中连边(i,j,w)。另附加面为点s*，无界面为t*。
    (G和G*的关系：面数=点数，点数=面数，边数=边数)
3.s*到t*的任意一条路径对应原图的一个割。求最短路径即可。

平面图相关知识：面数 = 边数-点数+2。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxv = 400*400+10;    //原图中最大的面数 = 2*n*(n-1)-n*n+2=(n-1)^2 + 1。
int mx[405][405];
struct Edge
{
    int to;
    int w;
    int next;
}e[6*maxv];
int head[maxv],edgeNum;
bool vis[maxv];
int dis[maxv];

void addEdge(int from, int to, int w)
{
    e[edgeNum].to = to;
    e[edgeNum].w = w;
    e[edgeNum].next = head[from];
    head[from] = edgeNum++;
}

int spfa(int start, int end)
{
    int i;
    queue<int> que;
    memset(vis,0,sizeof(vis));
    for(i = 0; i <= end; i++)
        dis[i] = INF;
    dis[start] = 0;
    vis[start] = true;
    que.push(start);
    while(!que.empty())
    {
        int now = que.front();
        que.pop();
        vis[now] = false;
        for(i = head[now]; i != -1; i = e[i].next)
        {
            int to = e[i].to;
            if(dis[now] + e[i].w < dis[to])
            {
                dis[to] = dis[now] + e[i].w;
                if(!vis[to])
                {
                    vis[to] = true;
                    que.push(to);
                }
            }
        }
    }
    return dis[end];
}

int main()
{
    int i,j;
    int t;
    int n;
    int now,right,down;
    scanf("%d",&t);
    while(t--)
    {
        edgeNum = 0;
        memset(head,-1,sizeof(head));
        scanf("%d",&n);
        for(i = 1; i <= n; i++)
            for(j = 1; j <= n; j++)
                scanf("%d",&mx[i][j]);
        int start = 0;
        int end = (n-1)*(n-1)+1;
        for(i = 1; i < n; i++)
        {
            for(j = 1; j < n; j++)
            {
                now = (i-1)*(n-1)+j;
                right = now + 1;
                down = now + n-1;
                if(j < n-1)
                {
                    addEdge(right,now,mx[i][j+1]);
                    addEdge(now,right,mx[i][j+1]);
                }
                if(i < n-1)
                {
                    addEdge(now,down,mx[i+1][j]);
                    addEdge(down,now,mx[i+1][j]);
                }
            }
        }
        for(j = 1; j < n; j++)
        {
            addEdge(start,j,mx[1][j]);
            addEdge((n-2)*(n-1)+j,end,mx[n][j]);
        }
        for(i = 1; i < n; i++)
        {
            addEdge(start,i*(n-1),mx[i][n]);
            addEdge((i-1)*(n-1)+1,end,mx[i][1]);
        }
        printf("%d\n",spfa(start,end));
    }
    return 0;
}