TCO 2013 Round 1A
第一次参加了TCO。。。比赛形式和TC一样。
凭借500侥幸PASS，应该是晋级了
250：直接枚举i,i+1，然后遍历所有的
500：这题是个大坑吧，第一反应是二分，显然是错的。
显然最优解必然会经过某个端点，那么枚举所有端点。然后再枚举跳到这个点的步数，这样子步长就有了，再判断是否可行。总体复杂度就是O(100*30000*50)大概就是这个样子。
后来好多人都FST，可能是卡了精度吧。写的时候要注意点，没想到我竟然过了
源文件不见了，代码拷不下来。。。
1000：费用流/匹配
对于每一个位置，拆成两个点，从源点到一个点流量为1，费用为0，从另外一个点到汇点流量为1，费用为0
然后考虑每一个位置的4个方向，如果是当前方向，则指向某个点，流量为1，费用为0，否则流量为1，费用为1。
这样的话，保证每一个点的入度出度为1，而且不会出现只经过1个点就到达汇点的，保证任意一个点都存在于且仅存在于某一个顶点数目>1的环中。
[cpp]
struct node{
int u,v,f,c,next;
}edge[500005];
int way[4][2]={0,1,0,-1,1,0,-1,0},idx=0;
int start[1005],dist[1005],vis[1005],pre[1005];
void _addedge(int u,int v,int flow,int cost){
edge[idx].u=u;edge[idx].v=v;edge[idx].f=flow;edge[idx].c=cost;
edge[idx].next=start[u];start[u]=idx++;
}
void addedge(int u,int v,int flow,int cost){
_addedge(u,v,flow,cost);
_addedge(v,u,0,-cost);
}
bool spfa(int s,int e,int n){
queue<int>que;
for(int i=0;i<n;i++){
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;
return 3;
}
int getMinimum(vector <string> b)
{
int n=b.size(),m=b[0].size();
idx=0;mem(start,-1);
for(int i=0;i<n;i++){
for(int j=0;j<m;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);
}
}
struct node{
int u,v,f,c,next;
}edge[500005];
int way[4][2]={0,1,0,-1,1,0,-1,0},idx=0;
int start[1005],dist[1005],vis[1005],pre[1005];
void _addedge(int u,int v,int flow,int cost){
edge[idx].u=u;edge[idx].v=v;edge[idx].f=flow;edge[idx].c=cost;
edge[idx].next=start[u];start[u]=idx++;
}
void addedge(int u,int v,int flow,int cost){
_addedge(u,v,flow,cost);
_addedge(v,u,0,-cost);
}
bool spfa(int s,int e,int n){
queue<int>que;
for(int i=0;i<n;i++){
