这道题本来G10跟我说是网络流的
然后我就直接写了个Dinic
于是
于是去搜了一下题解
发现是什么对偶图最短路。。对偶图最短路=最小割=最大流
因为这个图结构固定所以构造对偶图很简单
大概就是。。原来的每一块变成一个点，原来的边对应新图中的边
然后跑Dijkstra就完了
（虽然比别人写的还是慢点）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
// <1001.cpp> - 01/23/16 08:11:02 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } #define T (n-1)<<1,1 #define S (n-1)<<1,0 struct bian{ int x,y,k; bian(int a,int b,int c){x=a,y=b,k=c;} bool operator <(bian b) const {return k>b.k;} bool operator >(bian b) const {return k<b.k;} }; int n,m; int dis[2002][1002]; bool geng[2002][1002]; vector <bian>b[2002][1002]; priority_queue <bian> q; void make(int x,int y,int mx,int my,int k){ b[x][y].push_back(bian(mx,my,k)); b[mx][my].push_back(bian(x,y,k)); } int main(){ n=getint(),m=getint(); if(n==1||m==1){ if(m==1)swap(n,m); int ans=2147483647; for(int i=0;i<m-1;i++)ans=min(ans,getint()); printf("%d",ans); return 0; } for(int i=0;i<n;i++) for(int o=0;o<m-1;o++){ if(!i)make(i<<1,o,T,getint()); else if(i==n-1)make((i-1)<<1|1,o,S,getint()); else make(i<<1,o,(i-1)<<1|1,o,getint()); } for(int i=0;i<n-1;i++) for(int o=0;o<m;o++){ if(!o)make(i<<1|1,o,S,getint()); else if(o==m-1)make(i<<1,o-1,T,getint()); else make(i<<1|1,o,i<<1,o-1,getint()); } for(int i=0;i<n-1;i++) for(int o=0;o<m-1;o++) make(i<<1,o,i<<1|1,o,getint()); for(int i=0;i<(n-1)<<1;i++) for(int o=0;o<m-1;o++)dis[i][o]=2147483647; dis[(n-1)<<1][1]=2147483647; q.push(bian(S,0)); for(int i=0;i<((n-1)<<1)*(m-1)+2;i++){ int x=q.top().x,y=q.top().y;q.pop(); while(geng[x][y]){x=q.top().x,y=q.top().y;q.pop();} for(int i=0;i<b[x][y].size();i++){ int mx=b[x][y][i].x,my=b[x][y][i].y,mk=b[x][y][i].k; if(dis[x][y]+mk<dis[mx][my]){ dis[mx][my]=dis[x][y]+mk; q.push(bian(mx,my,dis[mx][my])); } } geng[x][y]=1; } printf("%d",dis[(n-1)<<1][1]); return 0; } |
说点什么