WA on Test6/Test8

Test6:

输入:

18 20
0 32 89 70 89 55 71 79 40 10 64 80 30 19 62 67 98 42 8 32 
57 27 22 1 38 89 52 74 43 8 2 65 82 20 67 22 43 22 95 16 
48 25 6 75 86 96 3 85 43 69 93 4 61 53 81 43 84 20 15 34 
22 35 26 28 33 67 19 79 19 45 8 13 51 0 86 68 18 47 82 3 
16 80 0 18 39 22 5 26 65 70 21 92 66 65 14 6 46 46 21 32 
80 35 86 6 67 29 42 71 14 77 55 3 1 14 38 71 82 41 65 12 
5 77 3 67 22 59 40 81 48 63 63 25 45 32 78 83 26 96 18 99 
45 56 31 30 45 47 80 1 7 81 18 1 90 15 71 22 69 44 18 31 
60 16 93 13 17 44 97 98 51 46 42 22 47 72 97 24 52 55 59 25 
100 28 5 14 76 32 41 97 61 32 20 0 2 8 41 52 77 35 22 98 
78 92 68 29 82 33 28 16 5 9 21 13 26 39 59 69 10 42 4 13 
80 34 42 100 44 32 70 15 32 8 83 10 23 73 8 53 7 21 10 52 
14 82 28 24 33 94 59 4 17 73 53 85 31 100 74 74 12 72 38 34 
14 22 53 0 30 95 3 52 79 41 36 81 25 24 67 48 95 44 7 96 
77 90 48 92 45 78 93 95 38 71 4 83 79 64 89 0 76 81 34 66 
1 13 58 4 40 5 24 17 6 65 13 13 76 3 20 8 36 12 60 37 
42 53 87 10 65 42 25 47 41 33 71 69 94 24 12 92 11 71 3 82 
91 90 20 95 44 76 60 34 95 49 40 89 4 45 27 9 34 82 59 0 

答案:

4419

程序输出:

16088

代码如下

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50005//最大点数
#define MAXM 500005//最大边数
#define INF 1061109567//最大容量
int n,m,S,T,tot,ans;//n-点数,m-边数,S-起点,T-终点
int l,h;
struct Edge{
	int t,w,c,s;//t-边的终点,w-最大容量,c-单位流量费用,s-剩余容量
}edge[MAXM];//边
int head[MAXN],nxt[MAXM],now[MAXN],dis[MAXN];//head-链式前向星队首,nxt-链式前向星下一个边,now-弧优化,cc-分层编号
vector<int>v[MAXN];
queue<int>q;
bool vis[MAXN];
int sumcost;//sumcost-最后支出的费用
inline void reset(){
	memset(vis,0,sizeof(vis));
	memset(head,-1,sizeof(head));
	memset(nxt,-1,sizeof(nxt));
	memset(now,-1,sizeof(now));
	return;
}
inline void input(int f,int t,int c,int w){//插入边,f-边起点,t-终点,w-边容量,c-单位流量费用
	// printf("%d %d %d %d\n",f,t,w,c);
	edge[tot].t=t;
	edge[tot].w=w;
	edge[tot].c=c;
	edge[tot].s=w;
	nxt[tot]=head[f];
	head[f]=tot;
	tot++;

	edge[tot].t=f;
	edge[tot].w=w;
	edge[tot].c=-c;
	edge[tot].s=0;
	nxt[tot]=head[t];
	head[t]=tot;
	tot++;
}
inline bool SPFA(){
	memset(dis,0x3f,sizeof(dis));
	memcpy(now,head,sizeof(now));
	q.push(S);
	dis[S]=0;
	vis[S]=1;
	while(!q.empty()){
		int top=q.front();
		q.pop();vis[top]=0;
		for(int i=head[top];i!=-1;i=nxt[i]){
			int tt=edge[i].t;
			if(edge[i].s&&dis[tt]>dis[top]+edge[i].c){
				dis[tt]=dis[top]+edge[i].c;
				if(!vis[tt]){
					q.push(tt);
					vis[tt]=1;
				}
			}
		}
	}
    return dis[T]!=INF;
}
int dfs(int x,int in){
	if(x==T) return in;
	vis[x]=1;
	int sum=0;
	for(int i=now[x];i!=-1&&in;i=nxt[i]){
		int tt=edge[i].t;
		now[x]=i;
		if(!vis[tt]&&edge[i].s&&dis[tt]==dis[x]+edge[i].c){
			int k=dfs(tt,min(edge[i].s,in));
			if(k) {
				sumcost+=k*edge[i].c;
				edge[i].s-=k;
				edge[i^1].s+=k;
				in-=k;
				sum+=k;
			}
			else dis[tt]=-1;
		}
	}
	vis[x]=0;
	return sum;
}
inline void dinic(){
	while(SPFA()){
		int k;
		while(k=dfs(S,INF)) ans+=k;
	}
	return;
}
inline int PC(int i,int j){return (i*l+j)*2;}
int main(){
	// freopen("P1006.out","w",stdout);
	memset(now,-1,sizeof(now));
	memset(head,-1,sizeof(head));
	memset(nxt,-1,sizeof(nxt));
    // S=0;T=1;
    scanf("%d%d",&l,&h);
    for(int i=1;i<=l;i++){
        for(int j=1;j<=h;j++){
            int k;
            scanf("%d",&k);
            if(i!=1) input(PC(i-1,j)^1,PC(i,j),0,INF);
            if(j!=1) input(PC(i,j-1)^1,PC(i,j),0,INF);
			if((i==1&&j==1)||(i==l&&j==h)) continue;
            input(PC(i,j),PC(i,j)^1,-k,1);
        }
    }
	S=PC(1,1);
	T=PC(l,h)^1;
    input(S,PC(1,1)^1,0,2);
    input(PC(l,h),T,0,2);
    dinic();
    printf("%d",-sumcost);
	return 0;
}