Luogu P2046. [NOI2010] 海拔

原文链接： https://www.shuizilong.com/house/archives/luogu-p2046-noi2010-%E6%B5%B7%E6%8B%94/

• https://www.luogu.com.cn/problem/P2046

简单的平面图最小割，难点是证这个是最小割。

代码主打的是一手对称。= =

 
  
#include <lastweapon/io> 
  
#include <lastweapon/dijkstra> 
  
 
  
using namespace lastweapon; 
  
 
  
int n, s, t; 
  
 
  
int id(int x, int y) { 
  
    if (x == -1 || y == n) return s; 
  
    if (x == n || y == -1) return t; 
  
    return x*n + y; 
  
} 
  
 
  
int main() { 
  
 
  
#ifndef ONLINE_JUDGE 
  
    freopen("in.txt", "r", stdin); 
  
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); 
  
#endif 
  
 
  
    RD(n); s=n*n; t=s+1; sp_graph<int> G(t+1); 
  
 
  
    REP(x, n+1) REP(y, n) G.add_edge(id(x-1,y), id(x,y), RD()); 
  
    REP(x, n) REP(y, n+1) G.add_edge(id(x,y), id(x,y-1), RD()); 
  
    REP(x, n+1) REP(y, n) G.add_edge(id(x,y), id(x-1,y), RD()); 
  
    REP(x, n) REP(y, n+1) G.add_edge(id(x,y-1), id(x,y), RD()); 
  
 
  
    cout << G.dijkstra(s, t) << endl; 
  
} 
  

本文转自： https://www.shuizilong.com/house/archives/luogu-p2046-noi2010-%E6%B5%B7%E6%8B%94/
本站仅做收录，版权归原作者所有。