题目链接:

http://codeforces.com/contest/330

A. Cakeminator

题目意思：

给一个r*c的矩阵方格，有些位置有S，如果某一行和一列都不含标记为S的方格，则可以把该行所有方格都收掉，问最多能收多少个方格，方格可以收多次，多次收的方格计数一次。

解题思路：

暴力

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

using namespace std;

/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

char save[15][15];

bool flag[15][15];

struct Point

{

   int x,y;

}pp[120];

int main()

{

   int r,c;

   while(scanf("%d%d",&r,&c)!=EOF)

   {

      int cnt=0;

      memset(flag,false,sizeof(flag));

      for(int i=1;i<=r;i++)

      {

         scanf("%s",save[i]+1);

         for(int j=1;j<=c;j++)

         {

            if(save[i][j]=='S')

            {

               pp[++cnt].x=i;

               pp[cnt].y=j;

            }

         }

      }

      for(int i=1;i<=r;i++) //扫描每一行

      {

         bool ff=true;

         for(int j=1;j<=c;j++) //如果都没有S，则标记这一行

            if(save[i][j]=='S')

            {

               ff=false;

               break;

            }

         if(ff)

            memset(flag[i],true,sizeof(flag[i]));//表示能收

      }

      for(int i=1;i<=c;i++) //扫描每一列

      {

         bool ff=true;

         for(int j=1;j<=r;j++)

            if(save[j][i]=='S')

            {

               ff=false;

               break;

            }

         if(ff)

            for(int j=1;j<=r;j++) //标记这一列

               flag[j][i]=true;

      }

      int ans=0;

      for(int i=1;i<=r;i++)

         for(int j=1;j<=c;j++)

            if(flag[i][j]) //统计计数

               ans++;

      printf("%d\n",ans);

   }

   return 0;

}

B. Road Construction
题目意思：

给一些不能连接的边，让你构造一幅图，使任意两点能互相到达，且经过的边数不超过2。

解题思路：

任意两个点之间的边数不超过2，说明该图一定是星图。找到中心的那个点（没有限制的边连接这点），直接连线即可。

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

using namespace std;

/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

int num[1100];

int main()

{

   int n,m;

   while(scanf("%d%d",&n,&m)!=EOF)

   {

      int a,b;

      memset(num,0,sizeof(num));

      for(int i=1;i<=m;i++) //num[i]表示i点的度数

      {

         scanf("%d%d",&a,&b);

         num[a]++,num[b]++;

      }

      int M=0;

      num[0]=INF;

      for(int i=1;i<=n;i++)

         if(num[i]<num[M]) //找到度数为零的点

            M=i;

      printf("%d\n",n-1);

      for(int i=1;i<=n;i++)

      {

         if(i==M)

            continue;

         printf("%d %d\n",i,M); //连接即可

      }

   }

   return 0;

}

C. Purification

题目意思：

给n*n的矩阵，让你放最少数量的清洗剂，使得所有的点都能清洗到，清洗剂所放位置的那一行和那一列的所有点都能清洗，其中E点不能放清洗剂。

解题思路：

如果能放，一定为n个，因为每一行或每一列都要扫描到。

如果每一行都有可放的位置，则输出每一行的任意一个能放的点即可，这样每一行的点都会清洗到。

如果每一列都有可放的位置，则输出每一列的任意一个能放得点即可，这样每一列的都会清洗到，也就达到了要求。

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

using namespace std;

/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

bool rr[120],cc[120];

char save[120][120];

vector<int>row[120];

vector<int>col[120];

int main()

{

   int n;

   while(scanf("%d",&n)!=EOF)

   {

      memset(rr,false,sizeof(rr));

      memset(cc,false,sizeof(cc));

      for(int i=1;i<=n;i++)

      {

         row[i].clear();

         col[i].clear();

      }

      for(int i=1;i<=n;i++)

      {

         scanf("%s",save[i]+1);

         for(int j=1;j<=n;j++)

         {

            if(save[i][j]=='.')

            {

               rr[i]=true,cc[j]=true; //当前行和列能扫描到

               row[i].push_back(j);

               col[j].push_back(i);

            }

         }

      }

      bool r=true,c=true; //是否所有的行或列能扫描到

      for(int i=1;i<=n;i++)

         if(!rr[i])

         {

             r=false;

             break;

         }

      for(int i=1;i<=n;i++)

         if(!cc[i])

         {

            c=false;

            break;

         }

      if(!r&&!c) //行或列都扫描不到

      {

         printf("-1\n");

         continue;

      }

      if(r) //如果行都能扫描到，直接输出每一行的第一个可以放的位置

      {

         for(int i=1;i<=n;i++)

            printf("%d %d\n",i,row[i][0]);

         continue;

      }

      if(c) //对于列 同理

      {

         for(int i=1;i<=n;i++)

            printf("%d %d\n",col[i][0],i);

         continue;

      }

   }

   return 0;

}

D. Biridian Forest

题目意思：

给一个n*m的矩阵，一个起始点和终点，矩阵中的数字表示该位置的魔鬼数量，当从起点到终点选择一条路径时，如果魔鬼能够在人之前或同时到达该路径某一位置，则人和魔鬼要打仗，选择一条路径，使得人与魔鬼打仗的个数最少。

解题思路：

该题主要是思维转换。bfs+贪心

假设人当前选择了一条路径C->D，终点为Ｄ，某处魔鬼B 能够和人C打仗，假设魔鬼在A位置与人打仗，则dis(B,A)<=dis(C,A)   =>dis(B,A,D)<=dis(C,D)   如果选择D终点，只需使得Min(dis(B,D))<=dis(C,D)   而dis(B,A,D)>=Min(dis(B,D))  所以对于某一特定路径，选择终点D打仗比其他任何一点都好。

如果选择从C-D的最短路，则能够打仗的魔鬼数量就最少。

代码：

#include<iostream>

#include<cmath>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

using namespace std;

/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

int dp[1100][1100],n,m;

char save[1100][1100];

bool vis[1100][1100];

int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

struct PP

{

   int x,y;

};

PP s,e;

void bfs() //找到终点到任何一点的最短距离

{

   queue<PP>myq;

   myq.push(e);

   while(!myq.empty())

   {

      PP f=myq.front();

      myq.pop();

      for(int i=0;i<4;i++)

      {

         int xx=f.x+dir[i][0],yy=f.y+dir[i][1];

         if((save[xx][yy]=='S'||(save[xx][yy]>='0'&&save[xx][yy]<='9'))&&!vis[xx][yy])

         {

            //printf(":%d %d\n",xx,yy);

            vis[xx][yy]=true;

            dp[xx][yy]=dp[f.x][f.y]+1;

            myq.push((PP){xx,yy});

         } //不在方格里的点为空的，不会扫描的

      }

   }

   return ;

}

int main()

{

   while(scanf("%d%d",&n,&m)!=EOF)

   {

      memset(vis,false,sizeof(vis));

      for(int i=1;i<=n;i++)

      {

         scanf("%s",save[i]+1);

         for(int j=1;j<=m;j++)

         {

            if(save[i][j]=='S')

               s.x=i,s.y=j;

            if(save[i][j]=='E')

               e.x=i,e.y=j,dp[i][j]=0,vis[i][j]=true;

         }

      }

     // printf("%d %d\n",e.x,e.y);

      bfs();

      int ans=0;

     // printf("%d\n",dp[s.x][s.y]);

      for(int i=1;i<=n;i++) //最短距离小的话，就直接加上

         for(int j=1;j<=m;j++)

            if(save[i][j]>'0'&&save[i][j]<='9'&&vis[i][j]&&dp[i][j]<=dp[s.x][s.y])

               ans+=save[i][j]-'0';

      printf("%d\n",ans);

   }

   return 0;

}

E. Graph Reconstruction

题目意思：

给一幅图，图中任意结点的度数至多为2。

让你重构一幅图，要求:图中节点和原来一样，边数数量也一样，任意节点度数至多为2.

解题思路：

题中所说的图的边数最多为n.

1、随机算法。

随机m个点，连成m条边，判断每一条边是否在给定的图里面，在的话，在随机，都不在，则满足题目要求，直接输出就行了。

2、构造法。

当n<=7,直接暴力判断

当n>7,一定存在一种构造满足题意。

构造方法：

因为每个点的度数最多为2，所以每一个联通块要么是一条线，要么是一个环，首先根据联通块将节点分成若*分。

然后将每一部分的节点的奇数位置节点提前。（保证相同部分的相邻节点之间的连线不冲突）

然后选择一个节点数量最多的那个部分，如果其节点数为偶数的话，交换头两个节点（防止环的情况尾和首相连有冲突），最后将其余各部分的节点从前之后依次插入。

最后按照给定的边数，从前之后输出相邻的两个节点构成一条边，如果需要把最后一个节点和第一个节点连起来。

代码：

#include<iostream>

#include<cmath>

#include<time.h>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<stack>

#include<list>

#include<queue>

#define eps 1e-6

#define INF 0x1f1f1f1f

#define PI acos(-1.0)

#define ll __int64

#define lson l,m,(rt<<1)

#define rson m+1,r,(rt<<1)|1

using namespace std;

/*

freopen("data.in","r",stdin);

freopen("data.out","w",stdout);

*/

vector<int>myv;

vector<int>vv[110000];

int n,m;

int main()

{

   srand((unsigned)(time(NULL)));

   while(scanf("%d%d",&n,&m)!=EOF)

   {

      int a,b;

      myv.clear();

      for(int i=1;i<=n;i++)

      {

         vv[i].clear();

         myv.push_back(i);

      }

      for(int i=1;i<=m;i++)

      {

         scanf("%d%d",&a,&b);

         vv[a].push_back(b);

         vv[b].push_back(a);

      }

      bool tt=false;

      for(int i=1;i<=500;i++) //随机次数

      {

         random_shuffle(myv.begin(),myv.end()); //随机节点

         bool flag=true;

         for(int j=0;j<m&&flag;j++) //看是否满足

         {

            int a=myv[j];

            int b=myv[(j+1)%n];

            for(int k=0;k<vv[a].size();k++)

               if(b==vv[a][k])

                  flag=false;

         }

         if(flag) //满足的话，直接输出

         {

            for(int j=0;j<m;j++)

               printf("%d %d\n",myv[j],myv[(j+1)%n]);

            tt=true;

            break;

         }

      }

      if(!tt)

         printf("-1\n");

   }

   return 0;

}