第一次參加了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++){ 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); } }
