最小割与最短路的转换(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;}?
?
?
?