本文共 3153 字，大约阅读时间需要 10 分钟。
题意：
给你一个n*n的矩阵，然后（0,0)为源点，(n - 1,n - 1)为汇点。点（i,j）可以到达（i + 1,j） (i,j + 1) 花费为a[i][j]。求从（0,0）到（n - 1,n - 1）的最小割。
思路：
如果按照正常建图，Dinic求最大流会超时，这里要充分利用平面图的性质。然后将其转化为对偶图，然后将求最大流最小割转化为求该图的对偶图最短路问题。
详细请参考：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define CL(arr, val) memset(arr, val, sizeof(arr))#define lc l,m,rt<<1#define rc m + 1,r,rt<<1|1#define pi acos(-1.0)#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define lowbit(x) (x)&(-x)#define Read() freopen("din.txt", "r", stdin)#define Write() freopen("dout.txt", "w", stdout)#define M 1000007#define N 407#define ll __int64using namespace std;const double eps = 1e-10;const int inf = 0x7f7f7f7f;struct node{ int v; int w; int next;}g[M];int head[N*N],ct;struct pnd{ int u; int ds; pnd() {} pnd(int x,int y) : u(x),ds(y){} bool operator < (const pnd &a) const { return ds > a.ds; }};int a[N][N];int n;int dis[N*N];bool vt[N*N];void add(int u,int v,int w){ g[ct].v = v; g[ct].w = w; g[ct].next = head[u]; head[u] = ct++; g[ct].v = u; g[ct].w = w; g[ct].next = head[v]; head[v] = ct++;}//int spfa(int s,int e)//{// int i;// for (i = 0; i <= e; ++i)// {// dis[i] = inf;// vt[i] = false;// }// dis[s] = 0;// vt[s] = true;// queue Q;// Q.push(s);// while (!Q.empty())// {// int u = Q.front(); Q.pop();// for (i = head[u]; i != -1; i = g[i].next)// {// int v = g[i].v;// if (dis[v] > dis[u] + g[i].w)// {// dis[v] = dis[u] + g[i].w;// if (!vt[v])// {// vt[v] = true;// Q.push(v);// }// }// }// vt[u] = false;// }//// return dis[e];//}int Dijkstra(int s,int e){ priority_queue pQ; for (int i = 0; i <= e; ++i) { dis[i] = inf; vt[i] = false; } dis[s] = 0; pQ.push(pnd(s,dis[s])); while (!pQ.empty()) { pnd ui = pQ.top(); pQ.pop(); if (vt[ui.u]) continue; vt[ui.u] = true; for (int i = head[ui.u]; i != -1; i = g[i].next) { int v = g[i].v; if (dis[v] > ui.ds + g[i].w) { dis[v] = ui.ds + g[i].w; pQ.push(pnd(v,dis[v])); } } } return dis[e];}int main(){// Read(); int T,i,j; scanf("%d",&T); while (T--) { scanf("%d",&n); for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) scanf("%d",&a[i][j]); CL(head,-1); ct = 0; int s = (n - 1)*(n - 1); int e = s + 1; int x; for (i = 0; i < n; ++i) { for (j = 0; j < n; ++j) { if (i == 0 && j != n - 1) { x = j; add(s,x,a[i][j]); } if (j == n - 1 && i != n - 1) { x = i*(n - 1) + (n - 2); add(s,x,a[i][j]); } if (j == 0 && i != n - 1) { x = i*(n - 1); add(x,e,a[i][j]); } if (i == n - 1 && j != n - 1) { x = (n - 2)*(n - 1) + j; add(x,e,a[i][j]); } if (i != n - 1 && j != n - 1) { if (i) { x = (i - 1)*(n - 1) + j; add((i*(n - 1) + j),x,a[i][j]); } if (j) { x = i*(n - 1) + j - 1; add((i*(n - 1) + j),x,a[i][j]); } } } } //优先队列优化的Dijkstra比spfa快多了。而且spfa时如果s,e链接边的只能是单向，否则会超时// printf("<
转载于:https://www.cnblogs.com/E-star/archive/2013/06/05/3118451.html
