本文主要是介绍最小割之平面图转最短路 CCF CSP[201703-5] 引水入城，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
平面图
设无向图G，若能将G画在一个平面上，使得任何两条边仅在顶点处相交，则称G是具有平面性质的图，简称平面图，否则称G是非平面图。
在平面图G中，G的边将其所在的平面划分成的区域称为面，有限的区域称为有限面或内部面，无限的区域称为无限面或外部面，包围面的边称为该面的边界，包围每个面的所有边组成的回路长度称为该面的次数。
摘自：https://www.cnblogs.com/lfri/p/9939463.html
给定一个平面图，图中的一个点为源点S，另外一个点为汇点T，且S和T都在图中的无界面的边界上，这样的平面图称为S-T平面图。
平面图的性质
- （欧拉公式）如果一个连通的平面图有n个点，m条边和f个面，那么f=m-n+2
- 每个平面图G都有一个与其对偶的平面图G*，G中的每个点对应G中的一个面，对于G中的每条边e有，e属于两个面f1、f2，加入边（f1，f2*）；e属于一个面f，加入边（f*，f*）。
平面图G与对偶图G*的关系
- G的面数等于G的点数，G和G的边数相同
- G*中的环与G中的割一一对应
理解：对有公共边的面之间会连一条边，自己连自己必定是无限面，无限面对应的G*中的点只有一个。
利用最短路求最小割
- 连接S和T，得到一个附加面；
- 对该图的对偶图G*，令附加面对应的点为S*，无界面对应的点为T*
- 删除S*和T*之间的边；
- 一条从S*到T*的路径，就对应了一个S-T割；
- 那么令G*中每条边的长度等于容量，那么最小割的容量就等于最短路的长度。
以上内容大部分摘自：周冬《两极相通——浅析最大—最小定理在信息学竞赛中的应用》
经典题型：引水入城
这是y总的题解，由于自己做出来总是段错误，这个题卡空间卡的太死，不得不抄下来y总的代码。仔细看会发现，这是每次求一层点到源点的最短距离，因为每一层都是一样的，很有规律支持这么做。
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 5050;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;int n, m, A, B, Q, X;
int c[N][N], r[N][N];
LL dis[N];int main(void)
{// freopen("in.txt", "r", stdin);scanf("%d%d%d%d%d%d", &n, &m, &A, &B, &Q, &X);for (int i = 1; i <= n - 1; i ++ )for (int j = 1; j <= m ; j ++ )c[i][j] = X = ((LL)A * X + B) % Q;for (int i = 2; i <= n - 1; i ++ )for (int j = 1; j <= m - 1; j ++ )r[i][j] = X = ((LL)A * X + B) % Q;for (int i = 1; i <= m - 1; i ++ ){for (int j = 1; j <= n - 1; j ++ ) dis[j] += c[j][i];for (int j = 2; j <= n - 1; j ++ ) dis[j] = min(dis[j], dis[j - 1] + r[j][i]);for (int j = n - 2; j >= 1; j -- ) dis[j] = min(dis[j], dis[j + 1] + r[j + 1][i]);}LL res = INF;for (int j = 1; j <= n - 1; j ++ )res = min(res, dis[j] + c[j][m]);printf("%lld\n", res);return 0;
}
这里是菜逼段错误的写法，9/14。
#include <bits/stdc++.h>
using namespace std;typedef long long LL;const LL INF = 1e18;
const int N = 5005;int n, m, A, B, Q, Xi, Xip;
int S, T, vis[N];
LL c[N][N], r[N][N], dis[N], X;struct Edge
{int to, w;Edge(int _to = 0, int _w = 0) : to(_to), w(_w) {}
};struct Node
{int id;LL dis;Node(int _id, LL _dis) : id(_id), dis(_dis) {}bool operator < (const Node & rhs) const{return dis > rhs.dis;}
};vector<Edge> e[N];void dijkstra()
{for (int i = 0; i <= T; i ++ ){dis[i] = INF;vis[i] = 0;}dis[S] = 0;priority_queue<Node> pq;pq.push(Node(S, 0));while (!pq.empty()){Node u = pq.top(); pq.pop();if (u.id == T) break;if (vis[u.id]) continue;vis[u.id] = 1;for (int i = 0; i < e[u.id].size(); i ++ ){Edge v = e[u.id][i];if (vis[v.to]) continue;if (dis[v.to] > v.w + u.dis){dis[v.to] = v.w + u.dis;pq.push(Node(v.to, dis[v.to]));}}}
}int main(void)
{// freopen("in.txt", "r", stdin);scanf("%d%d%d%d%d%d", &n, &m, &A, &B, &Q, &X);S = 0, T = (m - 1) * (n - 1) + 1;for (int i = 1; i <= n - 1; i ++ )for (int j = 1; j <= m ; j ++ )c[i][j] = X = (A * X + B) % Q;for (int i = 2; i <= n - 1; i ++ )for (int j = 1; j <= m - 1; j ++ )r[i][j] = X = (A * X + B) % Q;for (int j = 1; j <= n - 1; j ++ )e[S].push_back(Edge(j, c[j][1]));for (int i = 1; i <= m - 1; i ++ )for (int j = 1; j <= n - 1; j ++ ){int id = (i - 1) * (n - 1) + j;if (j != n - 1) e[id].push_back(Edge(id + 1, r[j + 1][i]));if (j != 1) e[id].push_back(Edge(id - 1, r[j][i]));if (i != 1) e[id].push_back(Edge(id - (n - 1), c[j][i]));if (i != m - 1) e[id].push_back(Edge(id + (n - 1), c[j][i + 1]));}for (int j = 1; j <= n - 1; j ++ )e[(m - 2) * (n - 1) + j].push_back(Edge(T, c[j][m]));dijkstra();printf("%lld\n", dis[T]);return 0;
}
这篇关于最小割之平面图转最短路 CCF CSP[201703-5] 引水入城的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
