TCO 2013 Round 1A (二)
ge(v,u,0,-cost);
}
bool spfa(int s,int e,int n){
queueque;
for(int i=0;i
return 3;
dist[i]=inf;vis[i]=0;pre[i]=-1;
}
que.push(s);dist[s]=0;vis[s]=1;
while(!que.empty()){
int u=que.front();
que.pop();
vis[u]=0;
for(int i=start[u];i!=-1;i=edge[i].next)
if(edge[i].f){
int v=edge[i].v;
if(dist[v]>dist[u]+edge[i].c){
dist[v]=dist[u]+edge[i].c;
pre[v]=i;
if(!vis[v]){
vis[v]=1;
que.push(v);
}
}
}
}
return dist[e]!=inf;
}
int MaxCostFlow(int s,int e,int n){
int ans=0,flow=inf;
while(spfa(s,e,n)){
ans+=dist[e];
for(int i=pre[e];i!=-1;i=pre[edge[i].u])
flow=min(flow,edge[i].f);
for(int i=pre[e];i!=-1;i=pre[edge[i].u]){
edge[i].f-=flow;
edge[i^1].f+=flow;
}
}
return ans;
}
class DirectionBoard
{
public:
int id(char ch){
if(ch=='R') return 0;
if(ch=='L') return 1;
if(ch=='D') return 2;
}
int getMinimum(vector b)
{
int n=b.size(),m=b[0].size();
idx=0;mem(start,-1);
for(int i=0;i
for(int j=0;j
int a=i*m+j+1,aa=a+n*m;
addedge(0,a,1,0);
addedge(aa,2*n*m+1,1,0);
for(int k=0;k<4;k++){
int x=(i+way[k][0]+n)%n;
int y=(j+way[k][1]+m)%m;
int v=x*m+y+1+n*m;
if(id(b[i][j])==k)
addedge(a,v,1,0);
else
addedge(a,v,1,1);
}
}
}
return MaxCostFlow(0,2*n*m+1,2*n*m+2);
}
}