平面图最小割->对偶图最短路
BZOJ题目传送门
洛谷题目传送门
最理想的情况当然是在某边道路上海拔从0变成1,而其它的海拔不变。这样总体力和就是这些边的权值和。
把权值看成容量的话就转变成一个最小割的问题。因为是平面图,可以转成对偶图的最短路来做。
顺便学了一发Dij+Heap。
其实挺套路的。主要建图很伤脑筋。我是右上为 S S ,左下为TT。
代码:
#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 505
#define M N*N
#define F inline
using namespace std;
struct edge{ int nxt,to,d; }ed[M<<];
struct P{ int x,d; };
int n,m,k,s,t,h[M],d[M];
priority_queue <P> q;
F char readc(){
static char buf[],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,,,stdin);
return l==r?EOF:*l++;
}
F int _read(){
int x=; char ch=readc();
while (!isdigit(ch)) ch=readc();
while (isdigit(ch)) x=(x<<)+(x<<)+(ch^),ch=readc();
return x;
}
#define addedge(x,y,z) ed[++k]=(edge){h[x],y,z},h[x]=k
F bool operator < (P a,P b){ return a.d>b.d; }
F int Dij(){
for (int i=;i<=t;i++) d[i]=;
q.push((P){s,});
while (!q.empty()){
if (q.top().d>d[q.top().x]) { q.pop(); continue; }
int x=q.top().x; q.pop();
for (int i=h[x],v;i;i=ed[i].nxt)
if (d[x]+ed[i].d<d[v=ed[i].to])
d[v]=d[x]+ed[i].d,q.push((P){v,d[v]});
}
return d[t];
}
int main(){
n=_read(),t=n*n+;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
addedge(max(s,(i-)*n+j),min(t,i*n+j),_read());
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (!j) addedge((i-)*n+,t,_read());
else if (j==n) addedge(s,i*n,_read());
else addedge((i-)*n+j+,(i-)*n+j,_read());
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
addedge(min(t,i*n+j),max(s,(i-)*n+j),_read());
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (!j) addedge(t,(i-)*n+,_read());
else if (j==n) addedge(i*n,s,_read());
else addedge((i-)*n+j,(i-)*n+j+,_read());
return printf("%d\n",Dij()),;
}