算法训练 Eurodiffusion

Eurodiffusion
/***********并未完全AC***********/

#include<iostream>

#include<algorithm>

#include<string.h>

using namespace std;

int c;//国家数目(即货币数目)

int cas=0;//测试组数

const int motif=1000000;

struct CTR{//存国家信息

    string name;//名称

    int x1,y1,xh,yh;//国家所在矩形的左下角和右上角

    bool fi;//是否完成

    int ft;//完成时间

    bool operator <(const CTR& ci)const{

    return ft<ci.ft||(ft==ci.ft&&name<ci.name);}

};

CTR ctr[25];

struct CTY{//存城市信息

    int rest[25],get[25];//rest[i]表示第i种货币余额，get[i]表示从其他城市得到的数量

    bool fi;//是否完成

    bool exist;//是否为可用的城市

    int belong;//属于哪个国家

};

CTY cty[25][25];//cty[x][y]表示点(x,y)上的城市

const int nextx[][2]={{1,0},{-1,0},{0,-1},{0,1}};//枚举四周的点

//这里写成next以后命名冲突了

void Init()//初始化

{

    memset(cty,0,sizeof(cty));

    printf("Case Number %d\n",++cas);

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

    {

        CTR& con=ctr[i];

        cin>>con.name>>con.x1>>con.y1>>con.xh>>con.yh;

        //scanf("%s%d%d%d%d",con.name,&con.x1,&con.y1,&con.xh,&con.yh);

        con.fi=0;con.ft=-1;

        for(int j=con.x1;j<=con.xh;j++)

        	for(int k=con.y1;k<=con.yh;k++)

        									{

            CTY& cit=cty[j][k];

            cit.exist=1;cit.fi=0;cit.rest[i]=motif;cit.belong=i;

        }

    }

}

void inflow(int x,int y)//货币流入

{

    CTY& cit=cty[x][y];

    if(!cit.exist) return;//当前城市不合法

    //int cnt=0;

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

    					{

        cit.rest[i]+=cit.get[i];

        cit.get[i]=0;

    }

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

    	if(cit.rest[i]<1)//货币库存不足1

    					{

        	cit.fi=0;

        	return;

    	}

    cit.fi=1;

    return;

}

void outflow(int x,int y)

{

    CTY& cit=cty[x][y];

    if(!cit.exist) return;//不合法

    int cnt=0;//周边城市个数

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

    {

        int nx=x+nextx[i][0];

        int ny=y+nextx[i][1];

        if(cty[nx][ny].exist)cnt++;

    }

    if(!cnt)return;//周边没有城市

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

    {

        int f=cit.rest[i]/1000;//要流出到每个城市的硬币

        cit.rest[i]-=cnt*f;//i种货币减少

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

        {

            int nx=x+nextx[j][0];

            int ny=y+nextx[j][1];

            if(cty[nx][ny].exist) cty[nx][ny].get[i]+=f;//i种货币流入

        }

    }

}

bool solve(int time)//模拟货币流通

{

    bool solved=1;//标记是否全部完成

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

    {

        int flag=0;

        CTR& con=ctr[i];

        for(int j=con.x1;j<=con.xh;j++)

        	for(int k=con.y1;k<=con.yh;k++)

        		inflow(j,k);//模拟货币流入

        for(int j=con.x1;j<=con.xh;j++)

        	for(int k=con.y1;k<=con.yh;k++)

        		if(!cty[j][k].fi)

        						{

            		con.fi=0;flag=1;break;

        		}

        if(!flag) con.fi=1;

        if(!con.fi) solved=0;//有国家未完成

        else if(con.ft==-1) con.ft=time;//避免重复更新

    }

    if(solved) return 1;//time时已经完成

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

    {

        CTR& con=ctr[i];

        for(int j=con.x1;j<=con.xh;j++)

        	for(int k=con.y1;k<=con.yh;k++)

        		outflow(j,k);//模拟货币流出

    }

    return 0;

}

int main()

{

    while(cin>>c&&c)

    {

        Init();

        int time=0;

        for(;;)

        	if(solve(time++)) break;

        sort(ctr,ctr+c);

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

        	cout<<"   "<<ctr[i].name<<"   "<<ctr[i].ft<<endl;

        	//printf("   %s   %d\n",ctr[i].name,ctr[i].ft);

    }

    return 0;

}
巴特西

算法训练 Eurodiffusion

最新文章

热门文章
