平面图

¶定义

画在平面上，任意两条边除顶点外无交点包围一个面的边的条数称为该面的次数

¶性质

欧拉公式：n - m + r = 2点数-边数+面数=2点数$n \geq 3$的平面图的边数$m \leq 3n-6$ (边数是线性的)

¶对偶图

每个面为一个顶点，对于平面图上的每条边（一定只与两个面相连），用边连接这两个面对应的顶点平面图最小割=对偶图最短路（对偶图的边权相当于割掉平面图一条边的代价，所以维护对偶图的连通性，等价于维护平面图的非连通性）G的面数等于G的点数， G与G的边数相同(每个面为一个点，每条边也对应了一条边)

¶P4001 [ICPC-Beijing 2006]狼抓兔子

求网格图的最小割网格图显然是平面图，转成对偶图后跑最短路即可然后对偶图难建还比网络流慢

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
const int N = 1e3 + 5;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
int n, m, S, T;
vector<pii> G[2*N*N];
ll dis[2*N*N];
bool vis[2*N*N];
void Dijkstra(int s)
{
  memset(dis, 0x3f, (T+1)*sizeof(ll));
  memset(vis, 0, (T+1)*sizeof(bool));
  dis[s] = 0;
  priority_queue<pli,vector<pli>,greater<pli>> q;
  q.push(mp(0, s));
  while(!q.empty())
  {
    int u = q.top().se; q.pop();
    if(vis[u]) continue;
    vis[u] = 1;
    for(auto it : G[u])
    {
      int v = it.fi, w = it.se;
      if(dis[v]>dis[u]+w)
      {
        dis[v] = dis[u] + w;
        q.push(mp(dis[v], v));
      }
    }
  }
}
int main()
{
  scanf("%d%d", &n, &m);
  S = 0, T = (2*n-2)*(m-1) + 1;
  auto id = [&](int x, int y) {
    if(x==0||y==m) return S;
    if(x==2*n-1||y==0) return T;
    return (x-1)*(m-1) + y;
  };
  for(int i=1; i<=n; i++)
    for(int j=1; j<m; j++)
    {
      int u = id(2*i-2, j), v = id(2*i-1, j), w; scanf("%d", &w);
      G[u].emplace_back(v, w); G[v].emplace_back(u, w);
    }
  for(int i=1; i<n; i++)
    for(int j=1; j<=m; j++)
    {
      int u = id(2*i-1, j-1), v = id(2*i, j), w; scanf("%d", &w);
      G[u].emplace_back(v, w); G[v].emplace_back(u, w);
    }
  for(int i=1; i<n; i++)
    for(int j=1; j<m; j++)
    {
      int u = id(2*i-1, j), v = id(2*i, j), w; scanf("%d", &w);
      G[u].emplace_back(v, w); G[v].emplace_back(u, w);
    }
  Dijkstra(S);
  printf("%lld\n", dis[T]);
  return 0;
}

¶牛客多校2 Interval

初始有一个区间$[1,n]$对于一个区间$[l,r]$(l<r)，可以变换成$[l+1,r]$,$[l,r-1]$,$[l−1,r]$,$[l,r+1]$现在给定m种方式，可以花费一定的代价限制某种变换，问最少花费多少代价使得区间$[1,n]$无法变换成长度为1的区间$n \leq 500$

¶做法

考虑网络流最小割建图，对每个区间建一个点，每种变换连边流量为INF，如果某种变换被限制，则连边流量为cost，表示割掉这条边的代价。点数是$n^2$,边数也是$n^2$的发现这是一个平面图，所以转成对偶图跑最短路就可以了

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define fi first
#define se second
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
const int N = 505;
constexpr ll LINF = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 1e9 + 7;
int n, m, S, T, idx[N][N], tot;
ll dis[N*N];
bool vis[N*N];
vector<pil> G[N*N];
inline void addedge(int u, int v, ll w)
{
  G[u].emplace_back(v, w);
  G[v].emplace_back(u, w);
}
void Dijkstra(int s)
{
  memset(dis, 0x3f, (tot+1)*sizeof(ll));
  memset(vis, 0, (tot+1)*sizeof(bool));
  dis[s] = 0;
  priority_queue<pli,vector<pli>,greater<pli>> q;
  q.push(mp(0, s));
  while(!q.empty())
  {
    int u = q.top().se; q.pop();
    if(vis[u]) continue;
    vis[u] = 1;
    for(auto it : G[u])
    {
      int v = it.fi; ll w = it.se;
      if(dis[v]>dis[u]+w)
      {
        dis[v] = dis[u] + w;
        q.push(mp(dis[v], v));
      }
    }
  }
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  for(int i=1; i<n; i++)
    for(int j=i; j<n; j++)
      idx[i][j] = ++tot;
  S = 0; T = ++tot;
  auto id = [&](int x, int y)
  {
    if(x==0) return S;
    if(y==n) return T;
    return idx[x][y];
  };
  for(int i=1; i<n; i++)
    for(int j=i; j<n; j++)
    {
      addedge(id(i-1, j), id(i, j), LINF);
      addedge(id(i, j), id(i, j+1), LINF);
    }
  for(int i=1; i<=n; i++) addedge(id(i, i), id(i-1, i-1), LINF);
  for(int i=1; i<=m; i++)
  {
    int l, r, c;
    char dir;
    cin >> l >> r >> dir >> c;
    if(dir=='L') addedge(id(l, r-1), id(l, r), c);
    else addedge(id(l-1, r-1), id(l, r-1), c);
  }
  Dijkstra(S);
  cout << (dis[T]>=LINF ? -1 : dis[T]) << '\n';
  return 0;
}