railqkk.cpp

本程序是关于火车车皮调度问题

#include"iostream.h"
#include"fstream.h"
#include"stdlib.h"
class Node
{
friend class Queue;
public:
	int data;
private:
	Node *next;
};
class Queue
{
public:
     Queue(){front=rear=0;}
     ~Queue(){}
	 void Enqueue(int in_x);
	 void Dequeue();
	 Node *front,*rear;
private:
	 int in_x;
};
void Queue::Enqueue(int in_x)
{
         Node *p1;
         p1=new Node;
         p1->data=in_x;
		 p1->next=0;
		 if(front)rear->next=p1;
         else front=p1;
         rear=p1;
}
void Queue::Dequeue()
{
	    Node *p;
        p=front;
        front=p->next;
        delete p;
}
int MIN(int mark_x,int mark_y,int mark_z,int mark_t)
{
if(mark_y>0&&mark_x>mark_y)
{
  mark_z=mark_t;
  mark_x=mark_y;
}
return 
  mark_z;

}
void main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");
	int number,*add,Qn,*car,a,*limit,startnow=0,Qx;
	
             in>>number>>Qn;
	if(in.fail()||number==0)
	         {out<<"No Solution!";
	          out.close();
              exit(1);}
    car=new int[number+1];
	for(a=1;a<=number;a++)
	    {in>>car[a];}
	limit=new int[Qn];
	add=new int[Qn];
	for(a=1;a<=Qn-1;a++)
	{in>>limit[a];
	add[a]=0;
	}
    Queue *queue;
	queue=new Queue[Qn];
	int NU,check=1;
	for(a=1;a<=number;a++)
    { NU=car[a];
	  int a=0,b=0,c=0,mark=0,fol=0,count=0,mark_x=0,mark_y=0,mark_z=0,mark_t=0;
loop:if(NU==check)
	  {
	    out<<0<<"->"<<Qn<<endl;
	    check++;
		NU=0;
		goto loop;
	  }
	  else
	  {
		for(Qx=1;Qx<Qn;Qx++)
		{
		    if(add[Qx]==0)
			{count++;
                if(b==0)
				{fol=Qx;b=1;}
		}
		    if(add[Qx]!=0&&queue[Qx].front->data==check)
			{
		        out<<Qx<<"->"<<Qn<<endl;
		        queue[Qx].Dequeue();
		        add[Qx]--;
		        check++;
				if(check<number+1)
		        goto loop;
				else
				{exit(1);}
			}
		    if(NU!=0&&add[Qx]!=0&&(NU-queue[Qx].rear->data)>0&&add[Qx]<limit[Qx])
			{
		     if(c==0)
			   {
                mark_x=(NU-queue[Qx].rear->data);
				mark=mark_z=Qx;
			    c=1;
			   }
	         else
			 {  
				mark_y=NU-queue[Qx].rear->data;
				mark_t=Qx;
			    mark=MIN(mark_x,mark_y,mark_z,mark_t);
			 }
			}
		}
	  	if(mark==0)
		{   
			if(NU!=0&&fol==0)
			{
				out.close();
				out.open("output.txt");
				goto next;
			}
			else
			{
			 if(NU!=0&&check!=(number+1))
			{queue[fol].Enqueue(NU);
			out<<0<<"->"<<fol<<endl; 
			add[fol]++;
			}
			}
		}
		else
		{   if(add[mark]<limit[mark])
		{
			queue[mark].Enqueue(NU);
			out<<0<<"->"<<mark<<endl;
			add[mark]++;}
		}
               
	  }
	}
	if(check==number+1)
	{exit(1);}
next:
	
    for(a=1;a<=Qn-1;a++)
	{
	add[a]=0;
	}
	Queue *nextqueue;
	nextqueue=new Queue[Qn];
	check=1;
	for(a=1;a<=number;a++)
    { NU=car[a];
	  int a=0,b=0,c=0,mark=0,fol=0,count=0,mark_x=0,mark_y=0,mark_z=0,mark_t=0;
nextloop:if(NU==check)
	  {
	    out<<0<<"->"<<Qn<<endl;
	    check++;
		NU=0;
		goto nextloop;
	  }
	  else
	  {
		for(Qx=1;Qx<Qn;Qx++)
		{
		    if(add[Qx]==0)
			{count++;
                if(b==0)
				{fol=Qx;b=1;}
		}
		    if(add[Qx]!=0&&nextqueue[Qx].front->data==check)
			{
		        out<<Qx<<"->"<<Qn<<endl;
		        nextqueue[Qx].Dequeue();
		        add[Qx]--;
		        check++;
				if(check<number+1)
				{goto nextloop;}
				else
				{exit(1);}
			}
		    if(NU!=0&&add[Qx]!=0&&(NU-nextqueue[Qx].rear->data)>0&&add[Qx]<limit[Qx])
			{
		     if(c==0)
			   {
                mark_x=(NU-nextqueue[Qx].rear->data);
				mark=mark_z=Qx;
			    c=1;
			   }
	         else
			 {  
				mark_y=NU-nextqueue[Qx].rear->data;
				mark_t=Qx;
			    mark=MIN(mark_x,mark_y,mark_z,mark_t);
			 }
			}
		}
		if(mark_x==1)
		{
		nextqueue[mark].Enqueue(NU);
		out<<0<<"->"<<mark<<endl;
		add[mark]++;
		}
		else
		{
	  	   if(fol!=0)
		   {   
			   nextqueue[fol].Enqueue(NU);
			   out<<0<<"->"<<fol<<endl;
			   add[fol]++;
		   }
		   else
		   {
			if(mark!=0)   
		   {
			nextqueue[mark].Enqueue(NU);
			out<<0<<"->"<<mark<<endl;
			add[mark]++;
		   }
			else
			{if(NU!=0)			
			{out.close();
             out.open("output.txt");
             out<<"No Solution!";
             out.close();
			 exit(1);}
		
			}

		   }
		}
               
	  }
	}
	






}