解题报告 之 SOJ3312 Stockholm Knights
Description
Time Limit: 4000 MS Memory Limit: 65536 K Description The city of Stockholm is a chessboard whose size is N*M. There are some Stockholm Knights in the city.Stockholm Knights are very special Knights.They only can move from a corner of a 3*4 grid to the opposite.For example, Stockholm Knights can move from (10,10) to(12,13) (12,7) (8,13) (8,7) (13,12) (7,12) (13,8) (7,8).There are some destinations in the city.And some grids of the city are destroyed which Stockholm Knights cannot step into.Every day, each knight can stay up, or choose to move to another position. Note that two knights cannot appear in the same grid on the same day. Can you tell me the minimal days needed tomake all destinations be occupied by Stockholm Knights? Input The first line of input is the number of test case.For each test case:The first line contains three integers N, M.The next N lines each contains M characters."*" represents free grid."#" for destroyed grid."D" for destination."K" for Stockholm Knight. There is a blank line before each test case.1<= N,M <= 30 Output For each test case output the answer on a single line:If you can make all destinations be occupied by Stockholm Knights less than 30 days, output the minimal days.Otherwise, just output ">30".Sample Input 75 7######D##########D##########K#####K3 4###D####K###3 7###*##########K#####D5 7K#####D##########*##########K#####D3 4***********K3 4***********D10 10#D#KKK#**K**###*KD##KK#****##K*D####K#####D#*####*#*D##*#*K##DKD##D####K#K#**D####K###**#*#*DK###K##Sample Output21230>308 Source 8th SCUPC
题目大意：果然SCUPC的题不是那么好做的。被此题完虐了。。。有一个城市是一个网格，给出一个地图的字符表示。有些格子上是可以站人的（. D K），有些格子上是不能站人的（#）。K表示有一个骑士，D表示目的地。每一秒中骑士可以向（4*3）或者（3*4）的格子走一次对角线，也可以不移动。问是否存在一个时刻，使得所有格子都同时被一个骑士占领（骑士可以不用完）。如果存在，则最小的时刻为多少？ 图解如下：
分析：首先需要了解时间动态流模型。如果不明白请参照经典例题：
SGU438 The Glorious Karlutka River
if (nx >= 1 && nx <= n&&ny >= 1 && ny <= m&&map[nx][ny] != ‘#’)
addedge( t * 2000 + (i – 1) * 30 + j + 1000, (t + 1) * 2000 + (nx – 1) * 30 + ny, 1 );
然后跑一下最大流，如果结果为D的数量则可以满足，继续二分。但其实此时还有一个错误，就是刚刚提到的每一个时间层的D格子并不是直接连接到des，而需要将坐标一样的点的所有时刻先汇总到subdes[i][j]，subdes[i][j]再连一条边到des。为什么呢？因为不同时间层的同一个D如果直接连到des，那么5s和10s的同一个D可能会传入两个流量，那么就错误了。因为要求某时刻某D只能有一个K。所以对于一个D，在不同的时间层里只能选择一个！
另外可以学习到的是这种时间层与网格状态结合的题，，节点的编号是很复杂的，建议使用宏定义。（虽然我没用。。。）
上代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<queue>using namespace std;const int MAXN = 82000;const int MAXM = 900000;const int INF = 0x3f3f3f3f;struct Edge{int from, to, cap, next;};Edge edge[MAXM];int head[MAXN];;int level[MAXN];char map[50][50];int mox[9] = { 0, 2, 2, -2, -2, 3, -3, 3, -3 };int moy[9] = { 0, 3, -3, 3, -3, 2, 2, -2, -2 };int src, des, cnt;void addedge( int from, int to, int cap ){edge[cnt].from = from;edge[cnt].to = to;edge[cnt].cap = cap;edge[cnt].next = head[from];head[from] = cnt++;swap( from, to );edge[cnt].from = from;edge[cnt].to = to;edge[cnt].cap = 0;edge[cnt].next = head[from];head[from] = cnt++;}int bfs( ){memset( level, -1, sizeof level );queue<int> q;while (!q.empty( ))q.pop( );level[src] = 0;q.push( src );while (!q.empty( )){int u = q.front( );q.pop( );for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (edge[i].cap > 0 && level[v] == -1){level[v] = level[u] + 1;q.push( v );}}}return level[des] != -1;}int dfs( int u, int f ){if (u == des)return f;int tem;for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (edge[i].cap > 0 && level[v] == level[u] + 1){tem = dfs( v, min( f, edge[i].cap ) );if (tem > 0){edge[i].cap -= tem;edge[i ^ 1].cap += tem;return tem;}}}level[u] = -1;return 0;}int Dinic( ){int ans = 0, tem;while (bfs( )){while ((tem = dfs( src, INF )) > 0){ans += tem;}}return ans;}int main(){int kase;cin >> kase;int n, m;src = 0;des = 81500;while (kase–){int d = 0;cin >> n >> m;memset( head, -1, sizeof head );cnt = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> map[i][j];if (map[i][j] == 'D') d++;}}//二分答案int low = 0, high = 31;int ans = 31;while (low <= high){memset( head, -1, sizeof head );cnt = 0;int mid = (low + high) / 2;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (map[i][j] == 'K')addedge( src, (i-1) * 30 + j, 1 );}}for (int t = 0; t <= mid; t++){for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if (map[i][j] != '#'){addedge( t * 2000 + (i – 1) * 30 + j, t * 2000 + (i – 1) * 30 + j + 1000, 1 );//拆点for (int k = 0; k <= 8; k++){int nx = i + mox[k];int ny = j + moy[k];if (nx >= 1 && nx <= n&&ny >= 1 && ny <= m&&map[nx][ny] != '#'){addedge( t * 2000 + (i – 1) * 30 + j + 1000, (t + 1) * 2000 + (nx – 1) * 30 + ny, 1 );}}}if (map[i][j] == 'D'){addedge( t * 2000 + (i – 1) * 30 + j + 1000, 31*2000+(i-1)*30+j, 1 );}}}}for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){if(map[i][j]=='D')addedge( 31 * 2000 + (i – 1) * 30 + j, des, 1 );}}if (Dinic()<d) low = mid + 1;else{ans = mid;high = mid – 1;}}if (ans>30)cout << ">30" << endl;elsecout << ans << endl;}return 0;}你们一个两百行是巧合么？不，那只是因为我是强迫症。
没有行李，没有背包，不带电脑更不要手机，
