题意：
给一个网格图，求其最小割。
题解：
A)把平面图转化为对偶图进行最短路求解。注意每个点的序号QAQ。
B)直接裸网络流。
参考代码：
A)对偶图最短路
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf= 0x7FFFFFFF;
const int MAXN=3e6+9;
const int MAXM=4e6+9;
int n,m;
struct Edge
{
int v,w,nxt;
} edge[MAXM*2];
int fir[MAXN],cnt=0;
void addedge(int u,int v,int w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].nxt=fir[u];
fir[u]=cnt++;
}
struct node
{
int u;
int d;
node(int u,int d):u(u),d(d) {}
bool operator < (const node &a) const
{
return d>a.d;
}
};
bool used[MAXN];
int dis[MAXN];
void dijkstra(int st)
{
priority_queue<node> que;
while(!que.empty())
que.pop();
for(int i=0;i<=(n-1)*(m-1)*2+1;i++)
dis[i]=inf;
dis[st]=0;
que.push(node(st,dis[st]));
memset(used,0,sizeof(used));
while(!que.empty())
{
int u=que.top().u;
que.pop();
if(used[u])
continue;
used[u]=1;
for(int i=fir[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
int w=edge[i].w;
if(used[v])
continue;
if(dis[v]>dis[u]+w)
{
dis[v]=dis[u]+w;
que.push(node(v,dis[v]));
}
}
}
}
int main()
{
memset(fir,-1,sizeof(fir));
scanf("%d%d",&n,&m);
if(n==1||m==1)
{
int ans=inf;
for(int i=1;i<max(n,m);i++)
{
int w;
scanf("%d",&w);
ans=min(ans,w);
}
printf("%d\n",ans);
return 0;
}
for(int i=1; i<=n; i++)
for(int j=1; j<m; j++)
{
int u,v,w;
scanf("%d",&w);
if(i==1)
{
u=0;
v=j*2;
}
else if(i==n)
{
u=((i-2)*(m-1)+j)*2-1;
v=(n-1)*(m-1)*2+1;
}
else
{
u=((i-2)*(m-1)+j)*2-1;
v=((i-1)*(m-1)+j)*2;
}
addedge(u,v,w);
addedge(v,u,w);
}
for(int i=1; i<n; i++)
for(int j=1; j<=m; j++)
{
int u,v,w;
scanf("%d",&w);
if(j==1)
{
u=((i-1)*(m-1)+j)*2-1;
v=(n-1)*(m-1)*2+1;
}
else if(j==m)
{
u=0;
v=((i-1)*(m-1)+j-1)*2;
}
else
{
u=((i-1)*(m-1)+j-1)*2;
v=((i-1)*(m-1)+j-1)*2+1;
}
addedge(u,v,w);
addedge(v,u,w);
}
for(int i=1; i<n; i++)
for(int j=1; j<m; j++)
{
int u,v,w;
scanf("%d",&w);
u=((i-1)*(m-1)+j)*2-1;
v=((i-1)*(m-1)+j)*2;
addedge(u,v,w);
addedge(v,u,w);
}
dijkstra(0);
printf( "%d\n",dis[(n-1)*(m-1)*2+1] );
return 0;
}B)dinic最大流
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct node
{
int v,w,nxt;
}edge[6000000];
int n,m,cnt,st,ed;
int fir[1001*1001],depth[1001*1001],cur[1001*1001];
void addedge(int u,int v,int w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].nxt=fir[u];
fir[u]=cnt++;
}
int dfs(int u,int flow)
{
if(u==ed)
return flow;
for(int& i=cur[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
int w=edge[i].w;
if(depth[v]==depth[u]+1&&w!=0)
{
int di=dfs(v,min(flow,w));
if(di>0)
{
edge[i].w-=di;
edge[i^1].w+=di;
return di;
}
}
}
return 0;
}
bool bfs()
{
queue<int> q;
while(!q.empty())
q.pop();
memset(depth,0,sizeof(depth));
depth[st]=1;
q.push(st);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=fir[u]; i!=-1; i=edge[i].nxt)
{
int v=edge[i].v;
int w=edge[i].w;
if(depth[v]==0&&w>0)
{
depth[v]=depth[u]+1;
q.push(v);
}
}
}
if(depth[ed]>0)
return 1;
else
return 0;
}
int dinic()
{
int tot=0;
while(bfs())
{
for(int i=1; i<=n*m; i++)
cur[i]=fir[i];
//memset(cur,0,sizeof(cur));
while(int temp=dfs(st,inf))
tot+=temp;
}
return tot;
}
int main()
{
scanf("%d%d",&n,&m);
cnt=0;
memset(fir,-1,sizeof(fir));
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m-1; j++)
{
int w;
scanf("%d",&w);
addedge((i-1)*m+j,(i-1)*m+j+1,w);
addedge((i-1)*m+j+1,(i-1)*m+j,w);
}
}
for(int i=1; i<=n-1; i++)
{
for(int j=1; j<=m; j++)
{
int w;
scanf("%d",&w);
addedge((i-1)*m+j,i*m+j,w);
addedge(i*m+j,(i-1)*m+j,w);
}
}
for(int i=1; i<=n-1; i++)
{
for(int j=1; j<=m-1; j++)
{
int w;
scanf("%d",&w);
addedge((i-1)*m+j,i*m+j+1,w);
addedge(i*m+j+1,(i-1)*m+j,w);
}
}
st=1; ed=n*m;
int ans=dinic();
printf("%d\n",ans);
return 0;
}