第一周的搜索

1.最短路计数 - 洛谷

求第一个点到每一个点的最短路的数量；

第一个点到第一个点的数量固定为1，由于边权为1，求最短路数量也就相当于求bfs搜索树的深度，因为每一个点的最短路都要经过连接它的上一个点，一次bfs就可以了。

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n,m;
int i;
int dep[1000001],vis[1000001],ans[1000001];
vector<int >v[1000001];
queue<int >q;
int main(){
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        if(a==b) continue;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dep[1]=0;vis[1]=1;ans[1]=1;q.push(1);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(i=0;i<v[x].size();i++){
            int y=v[x][i];
            if(!vis[y]){
                vis[y]=1;
                dep[y]=dep[x]+1;
                q.push(y);
            }
            if(dep[y]==dep[x]+1){
                ans[y]=(ans[x]+ans[y])%100003;
            }
        }
    }
    for(i=1;i<=n;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

2.封锁阳光大学 - 洛谷

用最少数量的河蟹封锁一张无向图，每只河蟹可以对一个点进行封锁，当某个点被封锁后，与这个点相连的道路就被封锁了，且河蟹不能相邻，做不到就输出Impossible；

对无向图中的每一个节点进行染色，由于河蟹不能相邻，所以相邻的节点不能使用同一种颜色，在对已经染色的点进行染色时，判断它当前的颜色与相邻的点是否相同，全部染色完成后，取两种颜色的较小值即可。

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
int head[10010],vis[10010],sum[3];
int i,ans=0,ant=0;
struct node{
    int t;int next;
}t[200010];
void add(int x,int y){
    ant++;
    t[ant].t=y;
    t[ant].next=head[x];
    head[x]=ant;
}
queue<int>q;
int BFS(int s){
    vis[s]=1;
    sum[1]=1;sum[2]=0;
    q.push(s);
    while(!q.empty()){
        int a=q.front();q.pop();
        for(i=head[a];i;i=t[i].next){
            int b=t[i].t;
            if(vis[b]==vis[a]) return 1;
            if(vis[b]==0){
                vis[b]=vis[a]%2+1;
                sum[vis[b]]++;
                q.push(b);
            }
        }
    }
    return 0;
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        add(a,b);
        add(b,a);
    }
    for(i=1;i<=n;i++){
        if(vis[i]) continue;
        if(BFS(i)){
            printf("Impossible");
            return 0;
        }
        else ans+=min(sum[1],sum[2]);
    }
    printf("%d",ans);
    return 0;
}

3.血色先锋队 - 洛谷

重生之我是卧底，计算每个领主被瘟疫感染的时间，汇报给巫妖王；

节点分为两种，一种是感染源，一种是领主，其他的杂兵不用管，从感染源开始进行bfs，将整个矩阵遍历，给每一个单位赋值，最后输出即可。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int map[510][510],vis[510][510],q[100010][2];
int i,j;
int ans=0;
int n,m,a,b;
void BFS(){
    int kp[4][2]={0,1,-1,0,1,0,0,-1};
    for(j=1;j<ans;j++){
        int x=q[j][0],y=q[j][1];
        vis[x][y]=1;
        for(i=0;i<4;i++){
            int xx=x+kp[i][0];int yy=y+kp[i][1];
            if(vis[xx][yy]) continue;
            if(xx<1||xx>n||yy<1||yy>m) continue;
            map[xx][yy]=map[x][y]+1;
            vis[xx][yy]=1;
            q[++ans][0]=xx;q[ans][1]=yy;
        }
    }
}
int main(){
    scanf("%d %d %d %d",&n,&m,&a,&b);
    for(i=1;i<=a;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        q[++ans][0]=x;q[ans][1]=y;
        vis[x][y]=1;
    }
    BFS();
    for(i=1;i<=b;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",map[x][y]);
    }
    return 0;
}

4.马的遍历 - 洛谷

重生之我是马，和卧底基本上一样，但是要注意遍历的时候要用象棋马的走法，就是马走日。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,m;
int i,j,ans=0;
int map[410][410],vis[410][410],q[200000][2];
int kp[8][2]={2,1,2,-1,-2,1,-2,-1,1,2,1,-2,-1,2,-1,-2};
void bfs(){
    int head=0;
    while(head<ans){
        head++;
        int x=q[head][0],y=q[head][1];
        vis[x][y]=1;
        for(i=0;i<8;i++){
            int xx=x+kp[i][0],yy=y+kp[i][1];
            if(xx<1||xx>n||yy>m||yy<1) continue;
            if(vis[xx][yy]) continue;
            vis[xx][yy]=1;
            map[xx][yy]=map[x][y]+1;
            q[++ans][0]=xx;q[ans][1]=yy;
        }
    }
}
int main(){
    int x,y;
    scanf("%d %d %d %d",&n,&m,&x,&y);
    q[++ans][0]=x;q[ans][1]=y;
    bfs();
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(map[i][j]==0&&(x!=i||y!=j)) printf("-1\t");
            else printf("%d\t",map[i][j]);
        }
        printf("\n");
    }
    return 0;
}

5.[USACO06FEB]Backward Digit Sums G/S - 洛谷

写出一个1至N的排列ai​，然后每次将相邻两个数相加，构成新的序列，再对新序列进行这样的操作，显然每次构成的序列都比上一次的序列长度少1，直到只剩下一个数字位置。下面是一个例子：

3,1,2,4

4,3,6

7,9

16

最后得到16这样一个数字。

现在想要倒着玩这样一个游戏，如果知道N，知道最后得到的数字的大小sum，请你求出最初序列ai​，为1至N的一个排列。若答案有多种可能，则输出字典序最小的那一个。

痛苦深搜，首先要想明白ai的相加与n的关系，简单排列一下（假设ai都为1）

n为4  1+3+3+1  n为5 1+4+6+4+1  n为6   1+5+10+10+5+1

其实就是杨辉三角每层的数字

有了每个数相加的个数，接下来就是枚举了，由于最后要求字典序，所以采用深搜，还可以进行一个枝的剪，当累计的和超过sum时，直接返回就可以了。

#include <bits/stdc++.h>
using namespace std;
int n,p;
int a[13];
int c[13][13];
bool b[13];
void dfs(int dep,int s)
{
    if(s>p)
        return;
    if(dep>n)
    {
        if(s==p)
        {
            cout<<a[1];
            for(int i=2;i<=n;i++)
                cout<<" "<<a[i];
            exit(0);
        }
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]==false)
        {
            b[i]=true;
            a[dep]=i;
            dfs(dep+1,s+i*c[n][dep]);
            b[i]=false;
        }
    }
}
int main()
{
    cin>>n>>p;
    c[1][1]=1;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    dfs(1,0);
    return 0;
}

6.求细胞数量 - 洛谷

一矩形阵列由数字 0 到 9 组成，数字 1 到 9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

发现不为0就进入dfs，同时把与它相邻的不为0的数字全部换成0，每发现一次就计数。由于输出的是一串数字，所以用char来绘制地图。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[101][101];
int ans=0;
void dfs(int x,int y) {
    if(x<1||y<1||x>n||y>m) {
        return ;
    }
    if(a[x][y+1]!='0') {
        a[x][y+1]='0';
        dfs(x,y+1);
    }
    if(a[x][y-1]!='0') {
        a[x][y-1]='0';
        dfs(x,y-1);
    }
    if(a[x+1][y]!='0') {
        a[x+1][y]='0';
        dfs(x+1,y);
    }
    if(a[x-1][y]!='0') {
        a[x-1][y]='0';
        dfs(x-1,y);
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a[i][j];
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            if(a[i][j]!='0') {
                a[i][j]=0;
                ans++;
                dfs(i,j);
            }
        }
    }
    printf("%d",ans);
    return 0;
}

7.取数游戏 - 洛谷

一个N×M的由非负整数构成的数字矩阵，你需要在其中取出若干个数字，使得取出的任意两个数字不相邻（若一个数字在另外一个数字相邻8个格子中的一个即认为这两个数字相邻），求取出数字和最大是多少。

也就是说取了一个数后，它周围的八个数不可以取，再从其他的数中取数，直到遍历完整个数字矩阵，可以使用dfs，在每一次取数后将周围的八个格子标记为不可取，回溯的时候在取消标记即可。

#include<bits/stdc++.h>
using namespace std;
int mp[10][10],vis[10][10];
int kp[8][2]={1,0,-1,0,0,1,0,-1,1,1,-1,1,1,-1,-1,-1};
int i,j,k,n,m,ans=0,ant=0;
void dfs(int x,int y){
    if(y==m+1){
        dfs(x+1,1);
        return;
    }
    if(x==n+1){
        ant=max(ant,ans);
        return;
    }
    dfs(x,y+1);
    if(vis[x][y]==0){
        ans+=mp[x][y];
        for(k=0;k<8;k++){
            ++vis[x+kp[k][0]][y+kp[k][1]];
        }
        dfs(x,y+1);
        for(k=0;k<8;k++){
            --vis[x+kp[k][0]][y+kp[k][1]];
        }
        ans-=mp[x][y];
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(mp,0,sizeof(mp));
        memset(vis,0,sizeof(vis));
        scanf("%d %d",&n,&m);
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                scanf("%d",&mp[i][j]);
            }
        }
        ant=0;
        dfs(1,1);
        printf("%d\n",ant);
    }
    return 0;
}

有奇怪的一点
            ++vis[x+kp[k][0]][y+kp[k][1]];
            --vis[x+kp[k][0]][y+kp[k][1]];
       改成

vis[x+kp[k][0]][y+kp[k][1]]=1；

vis[x+kp[k][0]][y+kp[k][1]]=0;后不知道为什么就行不通了。

8.[NOI2011] 道路修建 - 洛谷

就是一个树形结构，每条边对答案的贡献为边两边联通块大小差的绝对值乘上边权，输出边贡献之和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,cnt,ans;
int i;
int head[1000010],size[1000010];
struct node{
    int to,nt,t;
}nn[2000010];
void add(int a,int b,int c){
    cnt++;
    nn[cnt].to=b;
    nn[cnt].nt=head[a];
    nn[cnt].t=c;
    head[a]=cnt;
}
void dfs(int x,int y){
    size[x]=1;
    for(i=head[x];i;i=nn[i].nt){
        int to=nn[i].to;
        if(y==to) continue;
        dfs(to,x);
        size[x]+=size[to];
        ans+=nn[i].t*abs(size[to]*2-n);
    }
}
int main(){
    scanf("%d",&n);
    for(i=1;i<n;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    dfs(1,0);
    printf("%d",ans);
    return 0;
}