# include <iostream>
using namespace std;
# include <set>
# include <queue>
# include <string>
# define MAXNUM 99999999
struct point
{
	string str;
	int id;
};
class cmp
{
public:
	bool operator()(const point &a,const point &b) const
	{
		return a.str<b.str;
	}
};
class link
{
public:
	int c,f;
	bool used;
	link()
	{
		used=0;
		f=0;
	}
};
set<point,cmp> refer;
link g[800][800];
int vn=0,an=0,c=0,cn,list[1000];
void dfs(int pos,int level[])
{
	if(pos==c)
	{
		list[level[pos]]=pos;
		int min=MAXNUM;
		for(int i=1;i<level[pos];i++)
		{
			if(g[list[i]][list[i+1]].c&&g[list[i]][list[i+1]].c-g[list[i]][list[i+1]].f<min) 
				min=g[list[i]][list[i+1]].c-g[list[i]][list[i+1]].f;
			else if(!g[list[i]][list[i+1]].c&&g[list[i]][list[i+1]].f<min) 
				min=g[list[i]][list[i+1]].f;
		}
		for(int i=1;i<level[pos];i++)
		{
			if(g[list[i]][list[i+1]].c) 
				g[list[i]][list[i+1]].f+=min;
			else g[list[i]][list[i+1]].f-=min;
		}
	}
	else
	{
		list[level[pos]]=pos;
		for(int i=1;i<=c;i++)
		{
			if(g[pos][i].used&&level[i]==level[pos]+1&&((g[pos][i].c&&g[pos][i].c-g[pos][i].f>0)||(!g[pos][i].c&&g[pos][i].f)))
			{
				dfs(i,level);
			}
		}
	}
}

void makelevel(int level[])
{
	queue<int> q;
	level[c-1]=1;
	q.push(c-1);
	while(!q.empty())
	{
		int pos=q.front();
		q.pop();
		if(pos==c) break;
		for(int i=1;i<=c;i++)
			if(g[pos][i].used&&(!level[i]||level[i]>level[pos]+1)&&((g[pos][i].c&&g[pos][i].c-g[pos][i].f>0)||(!g[pos][i].c&&g[pos][i].f)))
			{
				level[i]=level[pos]+1;
				q.push(i);
			}
	}
}
int maxflow()//dicnic max-flow algorithm
{
	int level[800];
	memset(level,0,sizeof(level));
	makelevel(level);
    while(level[c])
	{
		dfs(c-1,level);
		memset(level,0,sizeof(level));
		makelevel(level);
	}
	int total=0;
	for(int i=1;i<=c;i++) if(g[c-1][i].used) total+=g[c-1][i].f;
	return total;
}

inline void add(int s,int e,int limit)
{
	g[s][e].c=limit;
	g[s][e].f=0;
	g[e][s].f=0;
	g[e][s].c=0;
	g[s][e].used=g[e][s].used=1;
}
int main()
{
	cin>>vn;
	int vnum[101];
	memset(vnum,0,sizeof(vnum));
	for(int i=1;i<=vn;i++)
	{
		point temp;
		cin>>temp.str;
		set<point,cmp>::iterator it=refer.find(temp);
		if(it==refer.end())
		{
			temp.id=++c;
			refer.insert(temp);
			vnum[c]++;
		}
		else //去重
		{
			vn--;
			i--;
			vnum[it->id]++;
		}
	}
	string t1[101],t2[101];
	cin>>an;
	int total=an;
	int anum[101];
	memset(anum,0,sizeof(anum));
	for(int i=1;i<=an;i++)
	{
		cin>>t1[i]>>t2[i];
		point temp;
		temp.str=t1[i];
		set<point,cmp>::iterator it=refer.find(temp);
		if(it==refer.end())
		{
			temp.id=++c;
			refer.insert(temp);
			anum[c-vn]++;
			
		}
		else
		{
			anum[it->id-vn]++;
			i--;
			an--;
		}
	}
	for(int i=1;i<=an;i++)
	{
		int s=vn+i,e;
		point temp;
		temp.str=t2[i];
		set<point,cmp>::iterator it=refer.find(temp);
		if(it==refer.end())
		{
			temp.id=++c;
			e=c;
			refer.insert(temp);
		}
		else e=it->id;
		add(s,e,MAXNUM);
	}
	cin>>cn;
	for(int i=1;i<=cn;i++)
	{
		point temp1,temp2;
		int s,e;
		cin>>temp1.str>>temp2.str;
		set<point,cmp>::iterator it1=refer.find(temp1),it2=refer.find(temp2);
		if(it1==refer.end())
		{
			temp1.id=++c;
			s=c;
			refer.insert(temp1);
		}
		else s=it1->id;
		if(it2==refer.end())
		{
			temp2.id=++c;
			e=c;
			refer.insert(temp2);
		}
		else e=it2->id;
		add(s,e,MAXNUM);
	}
	c++;
	for(int i=vn+1;i<=vn+an;i++)
	{
		add(c,i,anum[i-vn]);
	}
	c++;
	for(int i=1;i<=vn;i++)
	{
		add(i,c,vnum[i]);
	}
	cout<<total-maxflow()<<endl;
	return 0;
}
	
		

			
	
	

• Re:自虐下，最大流算法写错了。。。忘了修改回退边的流量，晕 (4082) yzhw 2009-05-02 02:48:03