题目大意

给你一个很大的网格图,求其最小割。

解题思路

拿到题,毫不犹豫地写了最小割即最大流,心想谁TM没事卡我Dinic啊。
然后不负众望地T掉了。
然后习得大法:平面图转对偶图。
这里就有一个定理:平面图的最小割 == 对偶图的最短路
至于为什么,我也不会证,你们可以去看一下这篇论文去理性愉悦一下:
周冬的论文 《两极相通——浅析最大—最小定理在信息学竞赛中的应用》

代码

读入部分写得比较丑,凑合着看看吧。。。

#include <bits/stdc++.h>

#define INF 2000000000
#define MAXS 2100000

using namespace std;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int N, M, S, T, Basic;
vector<int> edge[MAXS];
vector<int> len[MAXS];

void DEBUG();

void Special_Judge()
{
    if(N==1 && M==1)
    {
        printf("0");
        return;
    }
    int Ans = INF;
    if(N==1)
        for(int i=1; i<M; i++)
        {
            int x = read();
            Ans = min(Ans, x);
        }
    else
        for(int i=1; i<N; i++)
        {
            int x = read();
            Ans = min(Ans, x);
        }
    printf("%d", Ans);
}

void Add_edge(int x,int y,int le)
{
    edge[x].push_back(y);
    len[x].push_back(le);
    edge[y].push_back(x);
    len[y].push_back(le);
}

int Get_id(int x,int y) { return ((x-1)*(M-1)+y); }

void Add_heng_edge()
{
    int le;
    for(int i=1; i<M; i++)
    {
        le = read();
        Add_edge(S,Basic+i,le);
    }
    for(int i=2; i<N; i++)
        for(int j=1; j<M; j++)
        {
            le = read();
            Add_edge(Get_id(i-1,j),Basic+Get_id(i,j),le);
        }
    for(int i=1; i<M; i++)
    {
        le = read();
        Add_edge(Get_id(N-1,i),T,le);
    }
}

void Add_shu_edge()
{
    int le;
    for(int i=1; i<N; i++)
    {
        le = read();
        Add_edge(Get_id(i,1),T,le);
        for(int j=2; j<M; j++)
        {
            le = read();
            Add_edge(Basic+Get_id(i,j-1),Get_id(i,j),le);
        }
        le = read();
        Add_edge(Basic+Get_id(i,M-1),S,le);
    }
}

void Add_xie_edge()
{
    for(int i=1; i<N; i++)
        for(int j=1; j<M; j++)
        {
            int le = read();
            Add_edge(Get_id(i,j),Basic+Get_id(i,j),le);
        }
}

void Build_dual_graph()
{
    Basic = (N-1)*(M-1);
    S = 0; T = Basic*2+1;
    Add_heng_edge();
    Add_shu_edge();
    Add_xie_edge();
}

// Dijkstra
struct Heapnode{
    int node;
    int dis;
    bool operator < (const Heapnode& rhs) const{ return dis>rhs.dis; }
};
int dis[MAXS];
bool done[MAXS];
priority_queue<Heapnode> Q;

void Init_dij()
{
    for(int i=S; i<=T; i++)
    {
        dis[i] = INF;
        done[i] = false;
    }
    dis[S] = 0;
}

int Dijkstra()
{
    Init_dij();
    Q.push((Heapnode){S,0});
    while( !Q.empty() )
    {
        Heapnode x = Q.top(); Q.pop();
        int now = x.node;
        if(done[now]) continue;
        done[now] = true;
        int sz = edge[now].size();
        for(int i=0; i<sz; i++)
        if(dis[now]+len[now][i] < dis[edge[now][i]])
        {
            dis[edge[now][i]] = dis[now]+len[now][i];
            Q.push((Heapnode){edge[now][i], dis[edge[now][i]]});
        }
    }
    return dis[T];
}
// Dijkstra
void Solve()
{
    Build_dual_graph();
    //DEBUG();
    int Ans = Dijkstra();
    printf("%d", Ans);
}

void DEBUG()
{
    for(int i=S; i<=T; i++)
    {
        printf("#    %d:\n",i);
        int sz = edge[i].size();
        for(int j=0; j<sz; j++) printf("%d ",edge[i][j]);
        printf("\n");
        for(int j=0; j<sz; j++) printf("%d ",len[i][j]);
        printf("\n------------------------------------\n");
    }
}

int main()
{
    freopen("input.in","r",stdin);
    freopen("output.out","w",stdout);
    N=read(); M=read();
    if(N==1 || M==1) Special_Judge();
    else
    Solve();
    fclose(stdin); fclose(stdout);
    return 0;
}