本文共 2119 字，大约阅读时间需要 7 分钟。
题解：这个建图很简单，只要把（1，1）这个点作为超级源，（n，m）作为超级源就可以xjbp。空间要算好。dinic当前弧优化一下就可以跑1500ms
#include #include #include #include #include #include #include #include #include #include #include //#include //CLOCKS_PER_SEC#define se second#define fi first#define ll long long#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Pii pair #define Pli pair #define ull unsigned long long#define pb push_back#define fio ios::sync_with_stdio(false);cin.tie(0)const int N=6e6+10;const ull base=163;const int INF=0x3f3f3f3f;using namespace std;int n,m,s,t;int head[1000010],to[N],nx[N],cur[1000010];int cap[N];int tot=0;int d[1000010];inline int read(){ int x=0;char ch=getchar(); while (ch<'0'||ch>'9') ch=getchar(); while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x;}void add(int u,int v,int c){ to[tot]=v; cap[tot]=c; nx[tot]=head[u]; head[u]=tot++; to[tot]=u; cap[tot]=c; nx[tot]=head[v]; head[v]=tot++;}void init(){ tot=0; memset(head,-1,sizeof(head));}int bfs(){ memset(d,-1,sizeof(d)); queue q; q.push(s); d[s]=1; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];~i;i=nx[i]){ int v=to[i]; if(d[v]==-1&&cap[i]>0){ d[v]=d[u]+1; q.push(v); } } } return d[t]!=-1;}int dfs(int s,int a){ if(s==t||a==0)return a; int flow=0,f; for(int &i=cur[s];~i;i=nx[i]){ int v=to[i]; if(d[s]+1==d[v] && cap[i]>0 && (f=dfs(v,min(a,cap[i])))>0){ flow+=f; cap[i]-=f; cap[i^1]+=f; a-=f; if(a==0)break; } } return flow;}int dinic(){ int ans=0; while(bfs()){ for(int i=0;i<=t;i++)cur[i]=head[i]; while(int di=dfs(s,INF)){ ans+=di; } } return ans;}int getnum(int i,int j){ return (i-1)*m+j;}int main(){ n=read(),m=read(); s=1,t=n*m; memset(head,-1,sizeof(head)); int x,l1,l2; for(int i=1;i<=n;i++){ for(int j=1;j<=m-1;j++){ x=read(); l1=getnum(i,j),l2=l1+1; add(l1,l2,x); } } for(int i=1;i<=n-1;i++){ for(int j=1;j<=m;j++){ x=read(); l1=getnum(i,j),l2=l1+m; add(l1,l2,x); } } for(int i=1;i<=n-1;i++){ for(int j=1;j<=m-1;j++){ x=read(); l1=getnum(i,j),l2=l1+m+1; add(l1,l2,x); } } cout< <
转载于:https://www.cnblogs.com/Mrleon/p/9052790.html