Home > Old Blog Posts > USACO 1.4.4 Mother’s Milk

USACO 1.4.4 Mother’s Milk


BFS/DFS皆可,存储已经扩展过的状态,直到没有未扩展过的状态可扩展为止。

代码:

/*
ID: dementr1
PROG: milk3
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“milk3.in”);
ofstream fout(“milk3.out”);
struct bucket
{
int a[4];
} list[10000];
int v[4],closed,open;
void init()
{
fin>>v[1]>>v[2]>>v[3];
list[0].a[1]=list[0].a[2]=0;
list[0].a[3]=v[3];
}
bucket dao(bucket now,int i, int j)
{
bucket ans=now;

if(now.a[i]>=v[j]-now.a[j])
{
ans.a[i]=now.a[i]-(v[j]-now.a[j]);
ans.a[j]=v[j];
}
else
{
ans.a[i]=0;
ans.a[j]=now.a[i]+now.a[j];
}
return ans;
}
bool search(int n, bucket tmp)
{
int i;
for(i=0;i<=n;i++) if(tmp.a[1]==list[i].a[1]&&tmp.a[2]==list[i].a[2]&&tmp.a[3]==list[i].a[3]) return true;
return false;
}
void bfs()
{
int i,j;
closed=-1;
open=0;
while(closed<open)
{
closed++;
bucket tmp;
for(i=1;i<=3;i++)
for(j=1;j<=3;j++)
if(i!=j)
{
tmp=dao(list[closed],i,j);
if(!search(open,tmp))
{
open++;
list[open]=tmp;
}
}
}

}
void print()
{
bool ans[21];
int i,printer[21],num=0;
memset(ans,false,sizeof(ans));
for(i=0;i<=open;i++) if(list[i].a[1]==0) ans[list[i].a[3]]=true;
for(i=0;i<=20;i++) if(ans[i]) printer[num++]=i;
for(i=0;i<num-1;i++) fout<<printer[i]<<” “;
fout<<printer[num-1]<<endl;
}
int main()
{
init();
bfs();
print();
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: