HDU 4724 If You Know This,You Must Have NO GF 解题报告

zhongl

　　题目
　　题意：
　　Make一个文件有三种命令：
　　1、形如Target: [component ...]，表示要生成Target，必须要先有所有的components，如果某个component还不存在，就先生成它。如果还是不行，就不生成Target。依赖关系不会成环。
　　2、形如g++ a.o b.o -o main，完全可以忽略。
　　3、如果行中有‘#’，则‘#’后的是注释，不用管。
　　


　　如果一行最后有‘\'，表示和下一行是连在一起的，原本是同一行。
　　


　　这里的“This command will not get executed“有歧义，如果不能执行，究竟还是否生成那些能生成的components？我是能生成则生成，据说热身赛当天的标程是生成到第一个不能生成的component就停止。
　　


　　题解：
　　就一个模拟，将文件名分离出来，用数字代替，然后就会得到一棵依赖树，dfs一遍即可。
　　


　　

//Time:31ms
//Memory:372KB
//Length:2361B
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
#define MAXN 10005
map<string,int> ma;
int he[MAXN],to[MAXN],nex[MAXN],ntop,ans;
char s1[MAXN],s2[MAXN],*s3;
bool vi[600],ty[200];
void add(int u,int v)
{
to[ntop]=v;
nex[ntop]=he;
he=ntop&#43;&#43;;
}
bool cal(int h)
{
bool flag=true,f2=false;
if(vi[h])   return true;
for(int i=he[h];i!=-1;i=nex)
flag&=cal(to),f2=true;
vi[h]=flag&&f2;
ans&#43;=flag&&f2;
return vi[h];
}
char *mget(char *s)
{
if(s==NULL) return NULL;
for(int i=0,j=0;s&&s!='#';&#43;&#43;i)
if(ty[s])
{
for(;ty[s[i&#43;j]];&#43;&#43;j)    s2[j]=s[i&#43;j];
s2[j]='\0';
return s&#43;i&#43;j;
}
return NULL;
}
int main()
{
//freopen(&quot;/home/moor/Code/input&quot;,&quot;r&quot;,stdin);
int ncase,len,q,top,now;
scanf(&quot;%d&quot;,&ncase);
memset(ty,0,sizeof(ty));
for(int i=0;i<26;&#43;&#43;i)   ty[i&#43;'a']=ty[i&#43;'A']=1;
for(int i=0;i<10;&#43;&#43;i)    ty[i&#43;'0']=1;
ty['.']=1;
for (int hh=1;hh<=ncase;&#43;&#43;hh)
{
ntop=0;
top=1;
memset(he,-1,sizeof(he));
memset(vi,0,sizeof(vi));
ma.clear();
printf(&quot;%sCase #%d:\n&quot;,hh>1?&quot;\n&quot;:&quot;&quot;,hh);
s1[0]='\0';
while(gets(s1)&&(s1[0]=='\0'||s1[0]=='\n'||s1[0]=='\r'));
while(s1[0]!='=')
{
len=strlen(s1);
while(s1[len-1]=='\\')
{
gets(s2);
strcpy(&s1[len-1],s2);
len&#43;=strlen(s2)-1;
}
if(strstr(s1,&quot;:&quot;)==NULL)
{
gets(s1);
continue;
}
s3=s1;
s3=mget(s3);
if(ma.find(s2)==ma.end())       ma[s2]=top&#43;&#43;;
now=ma[s2];
while((s3=mget(s3))!=NULL)
{
if(ma.find(s2)==ma.end())       ma[s2]=top&#43;&#43;;
add(now,ma[s2]);
}
gets(s1);
}
scanf(&quot;%d&quot;,&q);
while(q--)
{
scanf(&quot;%s&quot;,s1);
if(ma.find(s1)!=ma.end())       vi[ma[s1]]=1;
}
scanf(&quot;%d&quot;,&q);
while(q--)
{
ans=0;
scanf(&quot;%s%s&quot;,s1,s2);
printf(&quot;%d\n&quot;,ma.find(s2)!=ma.end()?(cal(ma[s2])?ans:0):0);
}
gets(s1);
}
return 0;
}