USACO Betsy's Tour

算法很明显——DFS：从（1,1）点开始，向四个方向行走，每个点最多走一次，直到走到（N，1）点，并且总步数恰好等于N * N - 1。
可是，当N=7时，上面的算法要耗费好几分钟的时间。

有下面几种剪枝的方法（英文的是USACO提供的，本人用了加*号的）：

• If we use an array with a sentinel-buffer(哨兵) around the edges, we can avoid extra complexity introduced by further optimizations. Some speed is gained, too.(*)
• If we keep a running sum of the total number of squares touched in each column and in each row, we can check whether we have created a "wall" between the market and our current position, and prune these states.
• If we ever reach the right-hand wall at a distance vertically of Y without having touched the square at Y-1, we know we have created a wall in some shape that separates our current position with the square at Y-1. The same holds for every wall.
• keep track of the number of neighbor-squares that have been touched at each square. Each time we touch a square, we increment its neighbors' neighbor-sum. When a sum reaches 3, we know that we can stop because there is now a dead end at that square (unless we are going to that square next.) （这个剪枝很强大，不过我没有使用）
• 如果发现DFS当前到达点相邻的一个不是终点的点，其周围的点都被访问了，那么继续往下走就会形成一个永远无法到达的孤点，所以直接return。(*)
• 当前点左右都是已经点(包括边缘)，而上下都是未经点时，一定会有孤立的区域，return。同理，当前点上下都是已经点(包括边缘)，而左右都是未经点时，return。（来源于NOCOW）（*）

组合使用几个剪枝后，就可以很快的通过N=7的情况了，在USACO的机器上只要0.355s.

据说这道题还可以用“基于连通性的状态压缩动态规划”做，NOCOW上有代码。

本人的代码：

C语言: 高亮代码由发芽网提供

01 #include
02 #include
03
04 int N;
05 long cnt = 0;
06 int map[10][10] = {};
07 int dx[4] = {0,0,1,-1};
08 int dy[4] = {1,-1,0,0};
09
10 int isdest(int x,int y)
11 {
12     if(x == N && y == 1)    return 1;
13     return 0;
14 }
15
16 int checkaround(int x,int y)  //count way
17 {
18     int i;
19     int c = 0;
20     for(i = 0;i < 4;i ++)
21         if(map[x + dx[i]][y + dy[i]] == 0)
22             c ++;
23     return c;
24 }
25
26 void dfs(int x,int y,int d)
27 {
28     if(isdest(x,y))
29     {
30         if(d < N * N - 1)    return;
31         cnt ++;
32         return;
33     }
34     int k,nx,ny;
35     int mustcnt = 0,mustk;
36     if(map[x + 1][y] && map[x - 1][y] && !map[x][y - 1] && !map[x][y + 1])    return;
37     if(!map[x + 1][y] && !map[x - 1][y] && map[x][y - 1] && map[x][y + 1])    return;
38     for(k = 0;k < 4;k ++)
39     {
40         nx = x + dx[k];
41         ny = y + dy[k];
42         if(map[nx][ny] == 0)
43         {
44             if(!isdest(nx,ny) && checkaround(nx,ny) == 0)   //no way around new node,so it is an orphan node
45                 return;
46             if(!isdest(nx,ny) && checkaround(nx,ny) == 1)
47             {
48                 map[nx][ny] = 1;
49                 dfs(nx,ny,d + 1);
50                 map[nx][ny] = 0;
51                 return;
52             }
53                 map[nx][ny] = 1;
54                 dfs(nx,ny,d + 1);
55                 map[nx][ny] = 0;
56         }
57     }
58 }
59
60 void init()
61 {
62     int i,j;
63     for(i = 0;i <= N + 1;i ++)
64         for(j = 0;j <= N + 1;j ++)
65             map[i][j] = 1;
66     for(i = 1;i <= N;i ++)
67         for(j = 1;j <= N;j ++)
68             map[i][j] = 0;
69 }
70
71 int main()
72 {
73     freopen("betsy.in","r",stdin);
74     freopen("betsy.out","w",stdout);
75     scanf("%d",&N);
76     init();
77     map[1][1] = 1;
78     dfs(1,1,0);
79     printf("%ld\n",cnt);
80     return 0;
81 }

USACO Character Recognition

题目要求输出最接近输入数据的字符串，我们可以使用动态规划达到这个目的：
用opt[i]表示前i行最小的改变量，那么容易得出状态转移方程（叙述起来比较麻烦，请看代码114行～148行）。
由于题目要输出字符序列，因此使用prev,store分别记录前一个字符的开始位置和对应的字符。
不过，我第一次提交的程序在第8个测试点超时了。检查发现，每一次比较每两行字符的区别时，我使用的都是最朴素的方法，因为动态规划过程中要多次用到这些数据，这样以来就耗费了很多时间。于是，加上了linediff数组，用于储存font.in和charrec.in每行之间的差异，并预先计算（见36行init函数），需要时直接取出。

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define MAXLINE 1220
005 #define FONTN 27
006 #define INF 100000000
007
008 char corr[] = " abcdefghijklmnopqrstuvwxyz";
009 char font[FONTN][20][21];
010 int N;
011 char str[MAXLINE][21];
012 int opt[MAXLINE];
013 int prev[MAXLINE];
014 char store[MAXLINE];
015 int linediff[MAXLINE][FONTN][20];   //[line][fontnumber][fontline]  precalculate
016
017 void readfont()
018 {
019     int i,j;
020     freopen("font.in","r",stdin);
021     scanf("%d\n",&i);
022     for(i = 0;i < 27;i ++)
023         for(j = 0;j < 20;j ++)
024             scanf("%s\n",font[i][j]);
025 }
026
027 void readinput()
028 {
029     freopen("charrec.in","r",stdin);
030     scanf("%d\n",&N);
031     int i;
032     for(i = 0;i < N;i ++)
033         scanf("%s\n",str[i]);
034 }
035
036 void init()    //calculate linediff array
037 {
038     int i,j,k,t;
039     for(i = 0;i < N;i ++)
040         for(j = 0;j < FONTN;j ++)
041             for(k = 0;k < 20;k ++)
042             {
043                 linediff[i][j][k] = 0;
044                 for(t = 0;t < 20;t ++)
045                     if(font[j][k][t] != str[i][t])    linediff[i][j][k] ++;
046             }
047 }
048
049 int get_min(int a,int b)
050 {
051     if(a < b)    return a;
052     return b;
053 }
054
055 int cmp_normal(int l,int f)
056 {
057     int d;
058     int i;
059     for(i = d = 0;i < 20;i ++)
060         d += linediff[l ++][f][i];
061     return d;
062 }
063
064 int cmp_missing(int l,int f)
065 {
066     int d,tmp;
067     int missline,i,j;
068     d = INF;
069     for(missline = 0;missline < 20;missline ++)
070     {
071         tmp = 0;j = l;
072         for(i = 0;i < 20;i ++)
073         {
074             if(missline == i)    continue;
075             tmp += linediff[j ++][f][i];
076         }
077         d = get_min(d,tmp);
078     }
079     return d;
080 }
081
082 int cmp_dup(int l,int f)
083 {
084     int d,tmp;
085     int dupline,i,j;
086     d = INF;
087     for(dupline = 0;dupline < 20;dupline ++)
088     {
089         tmp = 0;j = l;
090         for(i = 0;i < 20;i ++)
091         {
092             if(i == dupline)
093             {
094                 tmp += get_min(linediff[j][f][i],linediff[j + 1][f][i]);
095                 j += 2;
096                 continue;
097             }
098             tmp += linediff[j ++][f][i];
099         }
100         d = get_min(d,tmp);
101     }
102     return d;
103 }
104
105 void dp()
106 {
107     int i,j;
108     //i:line
109     //j:alpha for test
110     int tmp;
111     opt[0] = 0;
112     for(i = 1;i < MAXLINE;i ++)
113         opt[i] = INF;
114     for(i = 0;i < N;i ++)
115     {
116         if(opt[i] == INF)    continue;
117         if(i + 19 <= N)
118             for(j = 0;j < 27;j ++)
119             {
120                 tmp = opt[i] + cmp_missing(i,j);
121                 if(tmp < opt[i + 19])
122                 {
123                     store[i + 19] = corr[j];
124                     opt[i + 19] = tmp;
125                     prev[i + 19] = i;
126                 }
127             }
128         if(i + 20 <= N)
129             for(j = 0;j < 27;j ++)
130             {
131                 tmp = opt[i] + cmp_normal(i,j);
132                 if(tmp < opt[i + 20])
133                 {
134                     store[i + 20] = corr[j];
135                     opt[i + 20] = tmp;
136                     prev[i + 20] = i;
137                 }
138             }
139         if(i + 21 <= N)
140             for(j = 0;j < 27;j ++)
141             {
142                 tmp = opt[i] + cmp_dup(i,j);
143                 if(tmp < opt[i + 21])
144                 {
145                     store[i + 21] = corr[j];
146                     opt[i + 21] = tmp;
147                     prev[i + 21] = i;
148                 }
149             }
150     }
151 }
152
153 void pt()
154 {
155     int i;
156     int top = 0;
157     char ans[100];
158     for(i = N;i > 0;i = prev[i])
159         ans[top ++] = store[i];
160     while(top --)
161         printf("%c",ans[top]);
162     printf("\n");
163 }
164
165 int main()
166 {
167     freopen("charrec.out","w",stdout);
168     readfont();
169     readinput();
170     init();
171     dp();
172     pt();
173     fclose(stdout);
174     fclose(stdin);
175     return 0;
176 }

USACO TeleCowmunication

这是一道和联通性有关的题目，USACO Chapter 4有介绍过解决这个题目的思路：

This is equivalent to the minimum node cut problem. The two given machines can be arbitrarily labeled the source and sink. The wires are bidirectional. Split each node into an in-node and an out-node, so that we limit the flow through any given machine to 1. Now, the maximum flow across this network is equivalent to the minimum node cut.（max-flow min-cut theorem, wikipedia）

To actually determine the cut, iterative remove the nodes until you find one which lowers the capacity of the network.

这个算法用到了“拆点”。在理解上述算法的前提下（后面说的一些概念是建立在“拆点”的图上的），仔细分析会发现，不“拆点”也可以，只需要修改一下最大流算法——找到增广路后直接删除路径上的点（除了始末两个），重复直到找不到增广路。这种算法的实质和上面的相同，复杂度也相同，不过实际运行会快一点。

得到了最大流后，以此尝试移除某个点，如果此时的最大流正好等于原来-1,那么这个点就是一个“关键点”。

最后，由于题目要输出排序最小的点集，于是进行一次DFS，然后移除点测试联通性即可。

上面说的相当混乱，看代码吧：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 int N,M,source,sink;
006 int cap[101][101] = {};
007 int tmp[101][101];
008 int queue[200];
009 int head,tail;
010 int exclude[101];
011 int oncut[101] = {};
012 int max;
013 int isdown[101] = {};
014
015 void enqueue(int node)
016 {
017     queue[tail ++] = node;
018 }
019
020 int dequeue()
021 {
022     return queue[head ++];
023 }
024
025 void init()
026 {
027     int a,b;
028     scanf("%d%d%d%d\n",&N,&M,&source,&sink);
029     while(M --)
030     {
031         scanf("%d%d\n",&a,&b);
032         cap[a][b] = cap[b][a] = 1;
033     }
034 }
035
036 int getmin(int a,int b)
037 {
038     if(a < b)    return a;
039     return b;
040 }
041
042 int prev[101];
043 int visit[101];
044 int flow[101];
045 int bfs()   //find augmenting path
046 {
047     int i,j;
048     head = tail = 0;
049     memset(flow,0,sizeof(flow));
050     memset(prev,0,sizeof(prev));
051     memset(visit,0,sizeof(visit));
052     enqueue(source);
053     visit[source] = 1;
054     flow[source] = 32000;
055     while(head < tail)
056     {
057         i = dequeue();
058         if(i == sink)
059             return flow[sink];
060         for(j = 1;j <= N;j ++)
061             if(tmp[i][j] > 0 && !visit[j] && !exclude[j])
062             {
063                 visit[j] = 1;
064                 flow[j] = getmin(flow[i],tmp[i][j]);
065                 prev[j] = i;
066                 enqueue(j);
067             }
068     }
069     return 0;
070 }
071
072 int solve()   //ford-fulkerson
073 {
074     int maxflow = 0;
075     int add,i;
076     memcpy(tmp,cap,sizeof(tmp));
077     while(1)
078     {
079         add = bfs();
080         if(add == 0)    break;
081         maxflow += add;
082         for(i = prev[sink];i != source;i = prev[i])   //exclude nodes on path
083             exclude[i] = 1;
084     }
085     return maxflow;
086 }
087
088 int reachable()   //whether source and sink are connected
089 {
090     int i,j;
091     head = tail = 0;
092     memset(visit,0,sizeof(visit));
093     enqueue(source);
094     visit[source] = 1;
095     while(head < tail)
096     {
097         i = dequeue();
098         if(i == sink)    return 1;
099         for(j = 1;j <= N;j ++)
100             if(cap[i][j] && !visit[j] && !isdown[j])
101             {
102                 visit[j] = 1;
103                 enqueue(j);
104             }
105     }
106     return 0;
107 }
108
109 void dfs(int node,int tot)
110 {
111     if(tot == max)
112     {
113         if(!reachable())
114         {
115             int i;
116             int flag = 1;
117             for(i = 1;i <= N;i ++)
118                 if(isdown[i])
119                 {
120                     if(flag)
121                     {
122                         flag = 0;
123                         printf("%d",i);
124                     }
125                     else
126                         printf(" %d",i);
127                 }
128             printf("\n");
129             exit(0);
130         }
131         return;
132     }
133     if(node > N)    return;
134     if(oncut[node])
135     {
136         isdown[node] = 1;
137         dfs(node + 1,tot + 1);
138         isdown[node] = 0;
139     }
140     dfs(node + 1,tot);
141 }
142
143 int main()
144 {
145     int i;
146     freopen("telecow.in","r",stdin);
147     freopen("telecow.out","w",stdout);
148     init();
149     max = solve();
150     printf("%d\n",max);
151     for(i = 1;i <= N;i ++) //find all "critical nodes"
152     {
153         if(i == source || i == sink)    continue;
154         memset(exclude,0,sizeof(exclude));
155         exclude[i] = 1;
156         if(solve() < max)
157             oncut[i] = 1;
158     }
159     dfs(1,0);
160     return 0;
161 }

同样附上“拆点”的代码，这个更方便理解：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004 #define INFINITY 32000
005
006 int N,M,source,sink;
007 int adj[101][101] = {};
008 int cap[210][210] = {};
009 int tmp[210][210];
010 int queue[210];
011 int head,tail;
012 int oncut[210] = {};
013 int max;
014 int isdown[210] = {};
015
016 void enqueue(int node)
017 {
018     queue[tail ++] = node;
019 }
020
021 int dequeue()
022 {
023     return queue[head ++];
024 }
025
026 void init()
027 {
028     int a,b;
029     scanf("%d%d%d%d\n",&N,&M,&source,&sink);
030     int i;
031     for(i = 1;i <= N;i ++)   split nodes----one in, one out
032         cap[i][N + i] = cap[N + i][i] = 1;   //split nodes
033     while(M --)
034     {
035         scanf("%d%d\n",&a,&b);
036         adj[a][b] = adj[b][a] = 1;
037         cap[a + N][b] = INFINITY;
038         cap[b + N][a] = INFINITY;
039     }
040 }
041
042 int getmin(int a,int b)
043 {
044     if(a < b)    return a;
045     return b;
046 }
047
048 int prev[210];
049 int visit[210];
050 int flow[210];
051 int bfs()
052 {
053     int i,j;
054     head = tail = 0;
055     memset(flow,0,sizeof(flow));
056     memset(prev,0,sizeof(prev));
057     memset(visit,0,sizeof(visit));
058     enqueue(source);
059     visit[source] = 1;
060     flow[source] = INFINITY;
061     while(head < tail)
062     {
063         i = dequeue();
064         if(i == sink)
065             return flow[sink];
066         for(j = 1;j <= N * 2;j ++)
067             if(tmp[i][j] > 0 && !visit[j])
068             {
069                 visit[j] = 1;
070                 flow[j] = getmin(flow[i],tmp[i][j]);
071                 prev[j] = i;
072                 enqueue(j);
073             }
074     }
075     return 0;
076 }
077
078 int solve()   //standard ford-fulkerson
079 {
080     int maxflow = 0;
081     int add,i;
082     memcpy(tmp,cap,sizeof(tmp));
083     while(1)
084     {
085         add = bfs();
086         if(add == 0)    break;
087         maxflow += add;
088         for(i = sink;i != source + N;i = prev[i])
089         {
090             tmp[prev[i]][i] -= add;
091             tmp[i][prev[i]] += add;
092         }
093     }
094     return maxflow;
095 }
096
097 int reachable()
098 {
099     int i,j;
100     head = tail = 0;
101     memset(visit,0,sizeof(visit));
102     enqueue(source);
103     visit[source] = 1;
104     while(head < tail)
105     {
106         i = dequeue();
107         if(i == sink)    return 1;
108         for(j = 1;j <= N;j ++)
109         {
110             if(adj[i][j] && !visit[j] && !isdown[j])
111             {
112                 visit[j] = 1;
113                 enqueue(j);
114             }
115         }
116     }
117     return 0;
118 }
119
120 void dfs(int node,int tot)
121 {
122     if(tot == max)
123     {
124         if(!reachable())
125         {
126             int i;
127             int flag = 1;
128             for(i = 1;i <= N;i ++)
129                 if(isdown[i])
130                 {
131                     if(flag)
132                     {
133                         flag = 0;
134                         printf("%d",i);
135                     }
136                     else
137                         printf(" %d",i);
138                 }
139             printf("\n");
140             exit(0);
141         }
142         return;
143     }
144     if(node > N)    return;
145     if(oncut[node])
146     {
147         isdown[node] = 1;
148         dfs(node + 1,tot + 1);
149         isdown[node] = 0;
150     }
151     dfs(node + 1,tot);
152 }
153
154 int main()
155 {
156     int i;
157     freopen("telecow.in","r",stdin);
158     freopen("telecow.out","w",stdout);
159     init();
160     max = solve();
161     printf("%d\n",max);
162     for(i = 1;i <= N;i ++)
163     {
164         if(i == sink || i == source)    continue;
165         cap[i][i + N] = cap[i + N][i] = 0;
166         if(solve() < max)
167             oncut[i] = 1;
168         cap[i][i + N] = cap[i + N][i] = 1;
169     }
170     dfs(1,0);
171     return 0;
172 }