BFS and DFS
A题：有两队，给出对立的两个人的编号，问最多可能一队有几个人。用不定数组记录每个人的对手，深搜每个连通图，用y的值区别两类，边搜变记录每队人数，累加较大的值。
#include<cstdio> #include<iostream> #include<cstring> #include<math.h> #include<algorithm> #include<vector> using namespace std; const int maxn = 20000 + 5; int vis[maxn]; int a,b; vector <int> vec[maxn]; void dfs(int x, int y) //两类人，y==1和y==2 { vis[x] = 1; if(y == 1) a++; //计数第一类的人数 else b++; //计数第二类的人数 for(int i = 0; i < vec[x].size(); i++) { int xn = vec[x][i]; if(!vis[xn]) dfs(xn, 3 - y); } } int main() { int t,n,u,v; scanf("%d",&t); int kas = 1; while(t--) { for(int i = 0; i < maxn; i++) vec[i].clear(); memset(vis,0,sizeof(vis)); scanf("%d",&n); while(n--) //把所有与i对立的存到vec[i]中 { scanf("%d%d",&u,&v); vec[u].push_back(v); vec[v].push_back(u); } int ans = 0; for(int i = 1; i < maxn; i++) //遍历所有人，累加人数多的一方 if(!vis[i] && vec[i].size()){ a = b = 0; dfs(i,1); ans += max(a,b); } printf("Case %d: %d\n",kas++,ans); } return 0; }B题：找与’@’连通的格子数。从’@’开始，搜索。
#include<cstdio> #include<iostream> #include<cstring> #include<math.h> #include<algorithm> #include<vector> using namespace std; const int maxn = 20 + 5; int vis[maxn][maxn]; int ans,w,h; int dir[4][2] = {{-1,0},{0,-1},{0,1},{1,0}}; void dfs(int x, int y) { if(x < 0 || x >= w || y < 0 || y >= h) return; if(vis[x][y]) return; vis[x][y] = 1; ans++; for(int i = 0; i < 4; i++) { int xn = x + dir[i][0]; int yn = y + dir[i][1]; dfs(xn, yn); } } int main() { int t,x,y; char c; scanf("%d",&t); int kas = 1; while(t--) { ans = 0; memset(vis,0,sizeof(vis)); scanf("%d%d",&h,&w); for(int i = 0; i < w; i++) { getchar(); for(int j = 0; j < h; j++) { scanf("%c",&c); if(c == '#') vis[i][j] = 1; else if(c == '@') x = i, y = j; else continue; } } dfs(x,y); printf("Case %d: %d\n",kas++,ans); } return 0; }D题：k号骑士一次能走k步（走日字形），求所有骑士走到同一个格子需要的最小次数。对每一个格子假设为终点，反向搜索到每个骑士需要的步数，再求次数。（代码下回再写吧）
E题：生成环的最小花费。深搜记录环，正反两个方向走，取最小值。（刚敲完莫名输出一直为零，后发现读入的时候以为n没用，写了while(n–)，后面用到了n。终于明白了为什么总让我们新设变量，不要改变题目所给量。切记！）
#include <iostream> #include <cstdio> #include <queue> #include <cmath> #include <cstring> #include <set> using namespace std; const int maxn = 100 + 5; int pic[maxn][maxn]; int vis[maxn]; int loop[maxn]; int n,p; void dfs(int e) //深搜找环，编号记录在loop数组里 { vis[e] = 1; loop[p++] = e; for(int i = 1; i <= n; i++) { if(!vis[i] && (pic[e][i] > 0 || pic[i][e] > 0)) dfs(i); } } int main() { int T; int a,b,c; scanf("%d",&T); for(int kas = 1; kas <= T; kas++) { memset(pic,0,sizeof(pic)); memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i = 0 ; i < n; i++) { scanf("%d%d%d",&a,&b,&c); pic[a][b] = c; } p = 0; dfs(1); loop[p] = 1; int ans1 = 0, ans2 = 0; //正逆向都搜一遍，取较小值 for(int i=0; i<p; i++) ans1 += pic[loop[i]][loop[i+1]]; for(int i=p; i>0; i--) ans2 += pic[loop[i]][loop[i-1]]; printf("Case %d: %d\n",kas,min(ans1,ans2)); } return 0; }剩下的还没做。
