题目描述
题解:
裸的最小割.
但是最大流跑不过去怎么办?
转变一下, 既然最大流是一条左下 <-> 右上的通路, 我们可以把图划分为若干区域,
最后找左下到右上的最短路就行了.
代码:
- #include<queue>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- typedef long long ll;
- const int N = 1100;
- template<typename T>
- inline void read(T&x)
- {
- T f = 1,c = 0;char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();}
- x = f*c;
- }
- int n,m,s,t,hed[2*N*N],cnt;
- int _id(int i, int j, int k) {
- if(i>n||j<1)return 0;
- if(i<1||j>m)return n*m<<1|1;
- return (i - 1) * m + j + k * n * m;
- }
- struct EG
- {
- int to,nxt;
- ll w;
- }e[6*N*N];
- void ae(int f,int t,ll w)
- {
- e[++cnt].to = t;
- e[cnt].nxt = hed[f];
- e[cnt].w = w;
- hed[f] = cnt;
- }
- struct Pair
- {
- int x;
- ll d;
- Pair(){}
- Pair(int x,ll d):x(x),d(d){}
- friend bool operator <(Pair a,Pair b){return a.d>b.d;}
- }tp;
- ll dis[2*N*N];
- bool vis[2*N*N];
- void dij()
- {
- priority_queue<Pair>q;
- memset(dis,0x3f,sizeof(dis));dis[s]=0;
- q.push(Pair(s,0));
- while(!q.empty())
- {
- tp = q.top();
- q.pop();
- int u = tp.x;
- if(vis[u])continue;
- vis[u]=1;
- for(int j=hed[u];j;j=e[j].nxt)
- {
- int to = e[j].to;
- if(dis[to]>dis[u]+e[j].w)
- {
- dis[to] = dis[u]+e[j].w;
- q.push(Pair(to,dis[to]));
- }
- }
- }
- }
- int main()
- {
- read(n),read(m);
- n--,m--;
- s = 0,t = n*m<<1|1;
- for(int i=1;i<=n+1;i++)
- for(int w,j=1;j<=m;j++)
- {
- read(w);
- ae(_id(i,j,1),_id(i-1,j,0),w);
- ae(_id(i-1,j,0),_id(i,j,1),w);
- }
- for(int i=1;i<=n;i++)
- for(int w,j=1;j<=m+1;j++)
- {
- read(w);
- ae(_id(i,j,0),_id(i,j-1,1),w);
- ae(_id(i,j-1,1),_id(i,j,0),w);
- }
- for(int i=1;i<=n;i++)
- for(int w,j=1;j<=m;j++)
- {
- read(w);
- ae(_id(i,j,0),_id(i,j,1),w);
- ae(_id(i,j,1),_id(i,j,0),w);
- }
- dij();
- printf("%lld\n",dis[t]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2944756.html