训练总结8.5

一、安排

学数据结构和图论时，也就上课听了一点，课后没复习也没做题。真是一点都没印象了，今天看了几道最小生成树的题，复习了一下课件，查了一下知识点。‘

二、题目

1、Curling 2.0

  找最短步数，一开始以为是个bfs，程序写好了一大半，结果发现好像有点不对，朝着特定方向搜索，应该是dfs？果真dfs可以实现，但是需要考虑的条件有点多，一开始还写的漏了好几个条件。

# include <cstdio> # include <iostream> # include <cstring> using namespace std; #define inf 0x7fffffff int sx,sy, re; int m, n; int mp[25][25]; int dir[4][2] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };

void dfs(int nowx,int nowy,int step) {     step++;     if(step > 10)         return;     for(int i = 0; i < 4; i++)     {         int nextx = nowx + dir[i][0];         int nexty = nowy + dir[i][1];         if(mp[nextx][nexty] == 1)             continue;         while(mp[nextx][nexty] == 0 || mp[nextx][nexty] == 2)         {             nextx += dir[i][0];             nexty += dir[i][1];         }         if(mp[nextx][nexty] < 0)             continue;         if(mp[nextx][nexty] == 1)         {             mp[nextx][nexty] = 0;             dfs(nextx - dir[i][0], nexty - dir[i][1], step);             mp[nextx][nexty] = 1;         }

        if(mp[nextx][nexty] == 3)         {             if(step < re)                 re = step;             continue;         }     } } int main() {     while(~scanf("%d%d", &m, &n) && (m || n))     {         re = inf;         memset(mp, -1, sizeof(mp));         for(int i = 1; i <= n; i++)             for(int j = 1; j <= m; j++)             {                 cin >> mp[i][j];                 if(mp[i][j] == 2)                 {                     sx = i;                     sy = j;                 }             }         dfs(sx, sy, 0);         if(re < inf)             cout << re << endl;         else             cout << -1 << endl;;     }     return 0; }

2、Shredding Company

分隔数字后相加，使其最接近并小于目标数。深搜。

#include <stdio.h> #include <string.h> #include <iostream> using namespace std;

char str[10]; int t, n, max_sum, step_sum; int v[10], vi[10]; int dis[1000000];

void dfs(int xi, int sum, int step)//xi记录进行了多少长度，sum记录和，step记录分了几部分； {     int i;     int flag;     if(xi >= n)     {         flag = 1;         for(i = 0; i < step; i++)//与现有最优解进行对比是否相同         {             if(v[i] != vi[i])             {                 flag = 0;                 break;             }         }         if(flag == 0)//不相同就记录下来         {             dis[sum] ++;         }         if(sum > max_sum)//寻找最优解         {             max_sum = sum;             step_sum = step;             for(i = 0; i < step; i++)             {                 vi[i] = v[i];             }         }         return;     }     int sum1 = 0;     for(i = xi; i < n; i++)     {         sum1 = sum1*10 + str[i] - '0';         if(sum1 + sum <= t)         {             v[step] = sum1;//记录每一段的数值             dfs(i+1, sum1 + sum, step+1);         }         else             break;     } }

int main() {     int i;     while(~scanf("%d%s", &t, str))     {         memset(v, 0, sizeof(v));         memset(vi, 0, sizeof(vi));         memset(dis, 0, sizeof(dis));         if(t==0 && strcmp(str, "0")==0)             break;         n = strlen(str);         int s = 0;         for(i = 0; i < n; i++)         {             s += str[i] - '0';         }         if(s > t)         {             printf("error\n");             continue;         }         max_sum = 0;         step_sum = 0;         dfs(0, 0, 0);         if(dis[max_sum] != 1)         {             printf("rejected\n");         }         else         {             printf("%d",max_sum);             for(i = 0; i < step_sum; i++)             {                 printf(" %d", vi[i]);             }             printf("\n");         }     }     return 0; }

3、Highways

  最小生成树的问题，这个一开始做的，没有用prim算法，这种思路也是可以接受的。但是一样的算法，在做下一题时WA了，完全不知道为什么。这个整整纠结了一下午，真心是一样的题，只是输出的结果不同。

  后来比较了一下，还是prim算法简单，以后还是用prim算法吧

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;

int mp[521][521]; int parent[521],high[521];

struct Node {     int x,y;     int data; }node[125011];

bool cmp(Node a,Node b) {     return a.data<b.data; }

int Find(int m) {     if(m==parent[m])         return m;     else         return parent[m]=Find(parent[m]); }

void unite(int x,int y) {     int fx,fy;  fx=Find(x);  fy=Find(y);  if(fx==fy) //两点已经连通，返回   return ;  if(high[fx]<high[fy])  //比较两根节点目前所在树的高度 ，低的连在高的上面，一样高则任意一个加一   parent[fx]=fy;

 else  {   parent[fy]=fx;   if(high[fx]==high[fy])             high[fx]++;  } }

int main() {     int T,n;     scanf("%d",&T);     while(T--)     {         scanf("%d",&n);         for(int i=1;i<=n;i++)             for(int j=1;j<=n;j++)                 scanf("%d",&mp[i][j]);         for(int i=1;i<=n;i++)         {             parent[i]=i;             high[i]=0;         }//初始化父节点和树的高度         int k=0,ans=0;         for(int i=1;i<=n;i++)         {             for(int j=i+1;j<=n;j++)             {                 node[k].x=i;                 node[k].y=j;                 node[k].data=mp[i][j];                 k++;             }         }//建树         sort(node,node+k,cmp);         for(int i=0;i<k;i++)         {             if(Find(node[i].x)!=Find(node[i].y))             {                 ans=max(ans,node[i].data);                 unite(node[i].x,node[i].y);             }         }         printf("%d",ans);     }     return 0; }

4、Agri-Net

这个是用prim算法解决的

#include<iostream> #include<cstring> #include<cstdio> using namespace std;

int node[101][101],vis[101],lowcost[101],n;

void prim() {     int next,Min,sum;     sum=0;     memset(vis,0,sizeof(vis));     for(int i=1;i<=n;i++)         lowcost[i]=node[1][i];     vis[1]=1;     for(int i=2;i<=n;i++)     {         Min=1000001;         for(int j=1;j<=n;j++)         {             if(!vis[j]&&Min>lowcost[j])             {                 Min=lowcost[j];                 next=j;             }         }         sum+=Min;         vis[next]=1;         for(int j=1;j<=n;j++)         {             if(!vis[j]&&lowcost[j]>node[next][j])                 lowcost[j]=node[next][j];         }     }     printf("%d\n",sum); }

int main() {     while(scanf("%d",&n)!=EOF)     {         for(int i=1;i<=n;i++)             for(int j=1;j<=n;j++)                 scanf("%d",&node[i][j]);         prim();     } }