(未完待续)
题目链接:Luogu P4001/BZOJ 1001/ICPC-Beijing 2006 Animal Run。
题目
题目描述
数据范围
$$3\leq n,m\leq 1000$$
时空限制
$$\text{Luogu}:3\text{s}/250\text{MiB}$$
$$\text{BZOJ}:15\text{s}/162\text{MiB}$$
$$\text{ICPC}:6\text{s}/+\infty\text{MiB}$$
题解
解法 A(网络流)
思路
把每条路径都作为边加入网络,用 $\text{Dinic}$ 求 $(1,1)$ 到 $(n,m)$ 的最小割即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
#define INF 0X3F3F3F3F
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg bool f=false;
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return f?-res:res;
}
const int MAXN=1000+5;
const int MAXM=1000+5;
inline void Read(void);
inline void Work(void);
int main(void){
Read();
Work();
return 0;
}
int n,m,s,t;
int cnt=1,head[MAXN*MAXM],to[MAXN*MAXM*6],w[MAXN*MAXM*6],Next[MAXN*MAXM*6];
inline void Add_Edge(reg int u,reg int v,reg int len){
Next[++cnt]=head[u];
to[cnt]=v;
w[cnt]=len;
head[u]=cnt;
return;
}
inline void Add_Tube(reg int u,reg int v,reg int len){
Add_Edge(u,v,len);
Add_Edge(v,u,len);
return;
}
inline int GetID(reg int i,reg int j){
return (i-1)*m+j;
}
inline void Read(void){
n=read(),m=read(),s=1,t=GetID(n,m);
for(reg int i=1;i<=n;++i)
for(reg int j=1;j<m;++j){
static int x;
x=read();
Add_Tube(GetID(i,j),GetID(i,j+1),x);
}
for(reg int i=1;i<n;++i)
for(reg int j=1;j<=m;++j){
static int x;
x=read();
Add_Tube(GetID(i,j),GetID(i+1,j),x);
}
for(reg int i=1;i<n;++i)
for(reg int j=1;j<m;++j){
static int x;
x=read();
Add_Tube(GetID(i,j),GetID(i+1,j+1),x);
}
return;
}
int dep[MAXN*MAXM];
queue<int> Q;
inline bool BFS(int s,reg int t){
memset(dep,-1,sizeof(dep));
while(!Q.empty())Q.pop();
dep[s]=1,Q.push(s);
while(!Q.empty()){
reg int ID=Q.front();
Q.pop();
for(reg int i=head[ID];i;i=Next[i])
if(dep[to[i]]==-1&&w[i]>0){
dep[to[i]]=dep[ID]+1;
Q.push(to[i]);
}
}
return dep[t]!=-1;
}
int cur[MAXN*MAXM];
inline int DFS(reg int ID,reg int t,reg int lim){
if(ID==t)
return lim;
reg int flow=0;
for(reg int &i=cur[ID];i;i=Next[i])
if(dep[to[i]]==dep[ID]+1&&w[i]>0){
reg int f=DFS(to[i],t,min(lim-flow,w[i]));
if(f){
flow+=f;
w[i]-=f;
w[i^1]+=f;
if(flow==lim)
break;
}
}
return flow;
}
inline int Dinic(reg int s,reg int t){
reg int res=0;
while(BFS(s,t)){
memcpy(cur,head,sizeof(head));
res+=DFS(s,t,INF);
}
return res;
}
inline void Work(void){
reg int ans=Dinic(s,t);
printf("%d\n",ans);
return;
}
解法 B(平面图转对偶图)
思路
平面图都可以转对偶图。
建立方法就是将平面图的每个面(包括外部面)看做一个节点。根据平面图上的每条边,将其划分的两个面所代表的顶点在对偶图中连接一条无向边,若边带权,则边权与原边相同。
接下来说这道题的做法。
首先想到解法 A(网络流)。但是复杂度太大了。
考虑平面图转化为对偶图的用处,根据这张从网上扒的图:

可知因为连接了外界的点,整个图存在一个经过 $s’−>t’$ 的环。实际上最小的环就是原图的最小割。
因为 $s’−>t’$ 这条边造成了环,所以删掉这条边,跑一遍 $s’−>t’$ 的最短路就是原图的最小割。
代码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define ll long long
#define pa pair<int,int>
using namespace std;
inline int read()
{
char ch=getchar(),lst;
int x=0;
while(ch<'0'||ch>'9')
{
lst=ch;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}return ((lst=='-')?-x:x);
}
int n,m,st=1,eend,head[2000009],cnt,dis[2000009];
const int inf=214748364;
bool vis[2000009];
struct Ed{
int to,nxt,dis;
}edge[7000009];
void add(int fr,int to,int dis)
{
cnt++;
edge[cnt].to=to;
edge[cnt].dis=dis;
edge[cnt].nxt=head[fr];
head[fr]=cnt;
}
void dij()//堆优化的dij
{
for(int i=1;i<=eend;i++)
dis[i]=inf;
dis[1]=0;
priority_queue<pa,vector<pa>,greater<pa> > q;
q.push(make_pair(0,1));
while(!q.empty())
{
int now=q.top().second;
q.pop();
if(vis[now])continue;
vis[now]=1;
for(int e=head[now];e;e=edge[e].nxt)
{
int v=edge[e].to,di=edge[e].dis;
if(dis[now]+di<dis[v])
{
dis[v]=dis[now]+di;
q.push(make_pair(dis[v],v));
}
}
}
}
int main()
{
n=read();m=read();
eend=(n-1)*2*(m-1)+2;
for(int i=1;i<=n;i++)//横边
{
for(int j=1;j<=m-1;j++)
{
int dis=read();
int ss=2*(i-1)*(m-1)+j+1;
int ee=ss-m+1;
if(i==1)
{add(ss,eend,dis);add(eend,ss,dis);
continue;}
if(i==n)
{add(st,ee,dis);add(ee,st,dis);
continue;}
add(ss,ee,dis);add(ee,ss,dis);
}
}//竖边
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
int dis=read();
int ss=j+(m-1)*(2*(i-1)+1)+1;
int ee=ss-m;
if(j==1)
{add(st,ss,dis);add(ss,st,dis);
continue;}
if(j==m)
{add(ee,eend,dis);add(eend,ee,dis);
continue;}
add(ee,ss,dis);add(ss,ee,dis);
}
}//斜边
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
{
int dis=read();
int ss=2*(i-1)*(m-1)+j+1;
int ee=ss+m-1;
add(ee,ss,dis);
add(ss,ee,dis);
}
}
dij();
printf("%d",dis[eend]);
}
近期评论