请教一下为什会超时(限时 15s)(我用了16秒)(最大流,对偶图)
//题目链接 http://www.#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int cnt,i,j,x,xx,xxx,h,t,s,hh[7010000],n,m,w;
bool dd[2010000];
int e,l[2010000],d[2010000];
struct node{
int v,next,z;
}b[6510000];
inline void add(int aa,int bb,int cc)
{
b[++cnt].v=bb;
b[cnt].next=hh[aa];
b[cnt].z=cc;
hh[aa]=cnt;
b[++cnt].v=aa;
b[cnt].next=hh[bb];
b[cnt].z=cc;
hh[bb]=cnt;
}
void add1()
{
for(i=1;i<m;++i)
{
scanf("%d",&x);
add(i*2,t,x);
}
for(i=2;i<n;++i)
{
for(j=1;j<m;++j)
{
scanf("%d",&x);
add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2-m*2+1,x);
}
}
for(j=1;j<m;++j)
{
scanf("%d",&x);
add(s,(n-2)*2*(m-1)+j*2-1,x);
}
}
void add2()
{
for(i=1;i<n;++i)
{
scanf("%d",&x);xx=(i-1)*(m-1)*2+1;
add(s,xx,x);
for(j=2;j<m;++j)
{
scanf("%d",&x);xx+=2;
add(xx-1,xx,x);
}
scanf("%d",&x);
add(xx+1,t,x);
}
}
inline void add3()
{
for(i=1;i<n;++i)
{
for(j=1;j<m;++j)
{
scanf("%d",&x);
add((i-1)*(m-1)*2+j*2,(i-1)*(m-1)*2+j*2-1,x);
}
}
}
void spfa()
{
dd[s]=true;
h=0;w=0;
memset(l,0x3f,sizeof(l));
l[s]=0;
while(1)
{
if(h>w)break;
for(i=hh[s];i;i=b[i].next)
{
e=b[i].v;
if(l[s]+b[i].z<l[e]){
l[e]=l[s]+b[i].z;
if(!dd[e])d[++w]=e,dd[e]=true;
}
}
dd[s]=false;
s=d[++h];
}
}
int main()
{
scanf("%d %d",&n,&m);
if(n==m&&n==1){
printf("0");
return 0;
}
s=0;
t=2*(n-1)*(m-1)+1;
add1();
add2();
add3();
spfa();
printf("%d",l[t]);
return 0;
}