new knowledge+1！

事情是这样的，博主在苦思冥想T4的过程中随机到了luogu P2046

一眼就看出来是网络流最小割，代码一敲：TLE

我开始思考，与T4一样，都是网格图，都是最小割，同样的TLE，不过我看到了这个

 ？？最短路是什么鬼

于是我点进题解发现了这个

经过短暂学习，故写下这篇博

前置知识：平面图与对偶图

先来说说平面图，平面图就是指能将一个图通过点边关系不交错的画在二维平面上的图

是不是很绕？ 

给你个示例就懂了

这个图通过这种方式画在平面上时除了点外边之间没有任何交叉点

为什么强调是“这种方式”呢，因为有些图画出来有交叉，但是还是平面图

 

这幅图中虽然有交叉，但是我们把3,4节点扭一下，还是没有任何交叉

平面图就说到这，接下来说对偶图

大家都听过欧拉公式吧（图论的）

在平面图G内 ，这说明了平面图中的点边割成许多面（废话）

抽象的一步来了，现在我们设身处地一下，有一个新的图G2 ，这个图每个点都只G中的一个面

而G2中两点有边相连，说明G中这两个面有隔着边相交的面

如图，我们就说红色图是黑色平面图的对偶图

很明显，这符合上述G与G2的关系，但也不难看出，对偶图中有可能有重边，因为两个面可能不止隔着一条边

T4 正解

内容详见我上一篇文章

好了，话说正题

我们原先解决这道题用的是最大流最小割定理的思路，即使使用HLPP解决时间复杂度也是O（n^5），这显然没啥优化常数的余地

现在我们用一种巧妙的方式

 

如图，先沿着S-T将整个图外面的面分为两半，定义为S'和T'，再画出原图的对偶图（显然网格图是平面图） 这里不是严谨的对偶图

因为所以在对偶图中的边一定对应一条原图的边，我们会发现一线非常神奇的事

所以S'-T'的路径都对应原图的一种割！

不严谨的证明很简单 ，显然这两个图均为我们在以上定义下的对偶图，因此一个图的路径必定割掉一些边使得其对偶图st不联通

所以我们依照这个建图，再跑一遍S'-T'的最短路

将总边权和-这个最短路径就好了 时间复杂度O（n^2log(n^2)）

能控在600ms内

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define N 510
#define cin io
#define cout io
using namespace std;
struct iost
{
	bool f; char c;
	int stk[12], tp;
	iost& operator>>(int& x)
	{
		f = false, x = 0;
	a:  c = getc(stdin), f = f || (c == '-'); if (c < '0' || c > '9') goto a;
	b:  x = (x << 1) + (x << 3) + (c & 0xf), c = getc(stdin); if (c >= '0' && c <= '9') goto b;
		return *this;
	}
	void prt(int x)
	{
		tp = 0;
	a:  stk[tp++] = x % 10, x /= 10; if (x) goto a;
	b:  putc(stk[--tp] | '0', stdout); if (tp) goto b;
	}
	iost& operator<<(const int& x)
	{
		if (x < 0) putc('-', stdout), prt(-x);
		else prt(x);
		putc(' ', stdout);
		return *this;
	}
}io;
struct point
{
	int x, y;
	bool ud;
};
struct msg
{
	point p;
	int dis;
	bool operator<(const msg& x)const { return dis > x.dis; }
};
struct Edge
{
	int nxt; point v; int w;
}E[N * N << 3];
int cnt, hd[N][N][2];
int n, m;
int dis[N][N][2], vis[N][N][2];
void adde(point u, point v, int w)
{
	E[++cnt] = { hd[u.x][u.y][u.ud],v,w };
	hd[u.x][u.y][u.ud] = cnt;
}
inline void dijkstra()
{
	priority_queue<msg> q;
	q.push({ {0,0,0},0 });
	while (!q.empty())
	{
		msg u = q.top(); q.pop();
		if (vis[u.p.x][u.p.y][u.p.ud]) continue;
		vis[u.p.x][u.p.y][u.p.ud] = 1;
		for (int i = hd[u.p.x][u.p.y][u.p.ud]; i; i = E[i].nxt)
		{
			point v = E[i].v; int w = E[i].w;
			if (dis[v.x][v.y][v.ud] > dis[u.p.x][u.p.y][u.p.ud] + w)
			{
				dis[v.x][v.y][v.ud] = dis[u.p.x][u.p.y][u.p.ud] + w;
				if (!vis[v.x][v.y][v.ud]) q.push({ v,dis[v.x][v.y][v.ud] });
			}
		}
	}
}
int sum;
int main()
{
	cin >> n >> m;
	static int ew;
	for (int i = 1; i <= m; i++)
	{
		cin >> ew;
		sum += ew;
		adde({ 0,0,0 }, { 1,i,1 }, ew);
		adde({ 1,i,1 }, { 0,0,0 }, ew);
	}
	for (int i = 1; i < n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> ew;
			sum += ew;
			adde({ i,j,0 }, { i + 1,j,1 }, ew);
			adde({ i + 1,j,1 }, { i,j,0 }, ew);
		}
	}
	for (int i = 1; i <= m; i++)
	{
		cin >> ew;
		sum += ew;
		adde({ n + 1,m + 1,0 }, { n,i,0 }, ew);
		adde({ n,i,0 }, { n + 1,m + 1,0 }, ew);
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> ew;
		sum += ew;
		adde({ i,1,0 }, { n + 1,m + 1,0 }, ew);
		adde({ n + 1,m + 1,0 }, { i,1,0 }, ew);
		for (int j = 1; j < m; j++)
		{
			cin >> ew;
			sum += ew;
			adde({ i,j,1 }, { i,j + 1,0 }, ew);
			adde( { i,j + 1,0 }, { i,j,1 },ew);
		}
		cin >> ew;
		sum += ew;
		adde({ i,m,1 }, { 0,0,0 }, ew);
		adde({ 0,0,0 }, { i,m,1 }, ew);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> ew;
			sum += ew;
			adde({ i,j,0 }, { i,j,1 }, ew);
			adde({ i,j,1 }, { i,j,0 }, ew);
		}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dis[i][j][0] = dis[i][j][1] = inf;
	dis[n + 1][m + 1][0] = inf;
	dijkstra();
	cout << sum - dis[n + 1][m + 1][0];
	return 0;
}