antladybug.cpp

蚂蚁与瓢虫的算法．．． 一个算法题目的解答

/*蚂蚁与瓢虫问题
  利用贪婪法，最短路径的算法，求得离瓢虫最近的蚂蚁的位置，既可完成题目要求
  输入：
  4
  1 2
  1 3
  2 4
  2
  1
  2
  2
  2
  4
  输出：
  1 0 
  4 2
*/

#include "iostream.h"
#include "malloc.h" 
#define MAX 9999

typedef struct{
	int position;//蚂蚁当前所在的位置
	int time;    //蚂蚁赶走瓢虫的次数
}AntState;       //定义一个蚂蚁状态的数据类型

typedef struct{
	int nodeNum;//图的结点个数
	int *adj;   //图的邻接矩阵
}Graphics;      //定义一个图的数据结构

//寻找离瓢虫最近的那个蚂蚁的函数
int ShortestRoute(Graphics Gra,int source,int AntNum,AntState *state){		
		double *powerData=(double*)malloc(sizeof(double)*Gra.nodeNum);  
		int *judge=(int*)malloc(sizeof(int)*Gra.nodeNum);
		int vex=0;
		int shortestAnt;
		double min,min1;
		int i,j,k;
		
		//将各结点的judge初始化为0
		for(i=0;i<Gra.nodeNum;i++)
			judge[i]=0;
		//设置powerData[i]的初值为起始结点与各结点的弧的权值
		for(i=0;i<Gra.nodeNum;i++){
			powerData[i]=Gra.adj[source*Gra.nodeNum+i];
		}
		judge[source]=1;
		for(i=0;i<Gra.nodeNum;i++){
			min=MAX;
			for(j=0;j<Gra.nodeNum;j++)
				if(judge[j]==0&&powerData[j]<min){
					min=powerData[j];
					vex=j;
				}
			judge[vex] = 1;//vex已经加入到第一组
			for(k=0;k<Gra.nodeNum;k++)
				if(judge[k]==0&&Gra.adj[vex*Gra.nodeNum+k]<MAX&&min<MAX&&min+Gra.adj[vex*Gra.nodeNum+k]<powerData[k])
                //从起始顶点到K的最小距离为从起始顶点到vex的min加上边adj[vex][k]
					powerData[k]=min+Gra.adj[vex*Gra.nodeNum+k];
		}
		min1=MAX;
		for(i=0;i<AntNum;i++){
			if(powerData[state[i].position-1]<min1){
				min1=powerData[state[i].position-1];
				shortestAnt=i;
			}
		}
		free(powerData);
		free(judge);
		return shortestAnt;
}

void main(){
	int i,j;
    int n,k,L;         //n为树上点的数目，k为蚂蚁兵的数目，L为瓢虫停留的次数
	int tempa,tempb;   //临时表示树上有边相连的两点
	int *ladybugPos;   //瓢虫停留的位置
	int shortestAnt;   //离瓢虫最近的蚂蚁所在的位置
	AntState *state;   //K个蚂蚁当前的状态
	Graphics Gra;      //用邻接矩阵表示树的结构
	while(true){
	    cin>>n;
        Gra.nodeNum=n;
	    Gra.adj=(int*)malloc(sizeof(int)*n*n);
	    for(i=0;i<Gra.nodeNum;i++)
		    for(j=0;j<Gra.nodeNum;j++){
			    if(i==j)
			        Gra.adj[n*i+j]=0;
			    else Gra.adj[n*i+j]=MAX;
			}              
	    for(i=0;i<n-1;i++){ //构建图的邻接矩阵
	        cin>>tempa>>tempb;
		    Gra.adj[n*(tempa-1)+tempb-1]=1;
		    Gra.adj[n*(tempb-1)+tempa-1]=1;
		}
	    cin>>k;
	    state=(AntState*)malloc(sizeof(AntState)*k);
	    for(i=0;i<k;i++){   //读入每个蚂蚁的初始状态
		    cin>>state[i].position;
		}
	    for(i=0;i<k;i++){   //将每个蚂蚁赶走瓢虫的数目初始化为0
		    state[i].time=0;
		}
	    cin>>L;
	    ladybugPos=(int*)malloc(sizeof(int)*L);
	    for(i=0;i<L;i++){
		    cin>>ladybugPos[i];//读入瓢虫的位置
		}
        for(i=0;i<L;i++){		
            shortestAnt=ShortestRoute(Gra,ladybugPos[i]-1,k,state);//找到离瓢虫最近的那个蚂蚁
		    state[shortestAnt].time++;                             //该蚂蚁赶走瓢虫的次数加1
		    state[shortestAnt].position=ladybugPos[i];             //该蚂蚁的位置变为瓢虫的位置
		}
	    for(i=0;i<k;i++)
	 	    cout<<state[i].position<<" "<<state[i].time<<endl;
	    free(state);
	    free(Gra.adj);
	    free(ladybugPos);
	}
}