一定要纪念这一天。
我这题调了整整一天。。。。。
2333
大概错了一个小地方，然后是两个建图的错误。
一是拆点，二是inf的是单向边。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 55 #define maxv 100050 #define maxe 10000050 #define inf 1000000007 using namespace std; int n,m,map[maxn][maxn],dis[maxv],nume=1,g[maxv],tot=0,lab[maxn][maxn],tab[maxv],max_flow=0; int stack[maxv],top=0,s,t,cnt=0; int s1[maxv],s2[maxv],t1=0,t2=0,cnts[maxn][maxn]; bool vis[maxn*maxn][maxn][maxn]; struct edge { int v,f,nxt; }e[maxe]; struct point { int x,y,d; point (int x,int y,int d):x(x),y(y),d(d) {} point () {} }p[maxv],en[maxv]; queue <int> q; int dx[]={0,-1,1,0,0},dy[]={0,0,0,-1,1}; char ss[maxn]; void addedge(int u,int v,int f) { e[++nume].v=v;e[nume].f=f; e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=0; e[nume].nxt=g[v];g[v]=nume; } bool judge(int x,int y) { return ((x>=1) && (x<=n) && (y>=1) && (y<=m) && (map[x][y]>=0)); } void build(int xx) { top=0; int x=p[xx].x,y=p[xx].y,d=p[xx].d,mx=0; if (d<=2) stack[++top]=s;else stack[++top]=t; if (judge(x+dx[d],y+dy[d])) { do { x+=dx[d];y+=dy[d]; if (map[x][y]>mx) {mx=map[x][y];stack[++top]=lab[x][y];en[xx]=point(x,y,0);vis[xx][x][y]=true;} }while (judge(x+dx[d],y+dy[d])); if (d<=2) for (int i=1;i<=top-1;i++) addedge(stack[i],stack[i+1],mx-tab[stack[i]]); else for (int i=1;i<=top-1;i++) addedge(stack[i+1]+cnt,stack[i]+cnt*(i!=1),mx-tab[stack[i]]); max_flow+=mx; } } void cross(int x,int y) { if ((max(p[x].d,p[y].d)<=2) || (min(p[x].d,p[y].d)>=3)) return; t1=0;t2=0;int xx,yy,d,retx=-1,rety=-1,pp=-1,qq=-1; int ex1,ey1,ex2,ey2; xx=p[x].x;yy=p[x].y;d=p[x].d; if (judge(xx+dx[d],yy+dy[d])) { do { xx+=dx[d];yy+=dy[d]; cnts[xx][yy]++; if ((xx==en[x].x) && (yy==en[x].y)) break; }while (judge(xx+dx[d],yy+dy[d])); } ex1=xx;ey1=yy; xx=p[y].x;yy=p[y].y;d=p[y].d; if (judge(xx+dx[d],yy+dy[d])) { do { xx+=dx[d];yy+=dy[d];cnts[xx][yy]++; if (cnts[xx][yy]==2) retx=xx,rety=yy; if ((xx==en[y].x) && (yy==en[y].y)) break; }while (judge(xx+dx[d],yy+dy[d])); } ex2=xx;ey2=yy; int flag1=0,flag2=0; while ((ex1!=p[x].x) || (ey1!=p[x].y)) { cnts[ex1][ey1]--; if ((map[ex1][ey1]) && (!flag1) && (retx!=-1) && (rety!=-1) && (vis[x][ex1][ey1])) pp=lab[ex1][ey1]; if ((ex1==retx) && (ey1==rety)) flag1=1; ex1-=dx[p[x].d];ey1-=dy[p[x].d]; } while ((ex2!=p[y].x) || (ey2!=p[y].y)) { cnts[ex2][ey2]--; if ((map[ex2][ey2]) && (!flag2) && (retx!=-1) && (rety!=-1) && (vis[y][ex2][ey2])) qq=lab[ex2][ey2]; if ((ex2==retx) && (ey2==rety)) flag2=1; ex2-=dx[p[y].d];ey2-=dy[p[y].d]; } if ((pp==-1) || (qq==-1)) return; if (p[x].d>=3) swap(pp,qq); addedge(pp,qq+cnt,inf); } bool bfs() { q.push(s); for (int i=s;i<=t;i++) dis[i]=inf; dis[s]=0; while (!q.empty()) { int head=q.front();q.pop(); for (int i=g[head];i;i=e[i].nxt) { int v=e[i].v; if ((e[i].f>0) && (dis[v]>dis[head]+1)) { dis[v]=dis[head]+1; q.push(v); } } } return dis[t]!=inf; } int dinic(int x,int low) { if (x==t) return low; int ret=0; for (int i=g[x];low && i;i=e[i].nxt) { int v=e[i].v; if (e[i].f>0 && dis[v]==dis[x]+1) { int dd=dinic(v,min(low,e[i].f)); ret+=dd;low-=dd; e[i].f-=dd;e[i^1].f+=dd; } } if (!ret) dis[x]=inf; return ret; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%s",ss); for (int j=1;j<=m;j++) { if ((ss[j-1]>='0') && (ss[j-1]<='9')) map[i][j]=ss[j-1]-'0'; else if (ss[j-1]=='.') map[i][j]=0; else { map[i][j]=-1; if (ss[j-1]=='A') p[++tot]=point(i,j,1); else if (ss[j-1]=='V') p[++tot]=point(i,j,2); else if (ss[j-1]=='<') p[++tot]=point(i,j,3); else p[++tot]=point(i,j,4); } } } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (map[i][j]>0) lab[i][j]=++cnt,tab[cnt]=map[i][j]; s=0;t=2*cnt+1; for (int i=1;i<=tot;i++) build(i); for (int i=1;i<=tot;i++) for (int j=i+1;j<=tot;j++) cross(i,j); while (bfs()) max_flow-=dinic(s,inf); printf("%d ",max_flow); return 0; }