#include <iostream> #include <vector> #include <map> #include <queue> #include <cstring> using namespace std; const int N=1e4+2,M=5e5; int n1,n2,n3,len; map<string,int> mp; map<int,int> A,B; const int inf =1e9+7; int aa[402][402]; int all=1,hd[N],go[M],w[M],nxt[M]; int S,T,n,m; int dis[M],ans=0,now[M]; void add_(int x,int y,int z){ nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=z; swap(x,y); nxt[++all]=hd[x]; hd[x]=all; go[all]=y; w[all]=0; } bool bfs(){ for(int i=0;i<M;i++)dis[i]=inf; queue<int> q; q.push(S); now[S]=hd[S]; dis[S]=0; while(q.empty()==0){ int x=q.front(); q.pop(); for(int i=hd[x];i;i=nxt[i]){ int y=go[i]; if(w[i]>0&&dis[y]==inf){ dis[y]=dis[x]+1; now[y]=hd[y]; q.push(y); if(y==T) return 1; } } } return 0; } int dfs(int x,int sum){ if(x==T) return sum; int k,res=0; for(int i=now[x];i&& sum ;i=nxt[i]){ now[x]=i; int y=go[i]; if(w[i]>0&&(dis[y]==dis[x]+1)){ k=dfs(y,min(sum,w[i])); if(k==0) dis[y]=inf; w[i]-=k; w[i^1]+=k; res+=k; sum-=k; } } return res; } void clear(){ memset(aa,0,sizeof aa); mp.clear(); A.clear(); B.clear(); memset(hd,0,sizeof hd);all=1; } void sov(int cas){ int i,j ; string s,s2; clear(); len=0; cin>>n1; for(i=1;i<=n1;i++){ cin>>s; if(!mp.count(s)) mp[s]=++len; A[i]=mp[s]; } cin>>n2; for(i=1;i<=n2;i++){ cin>>s>>s2; if(!mp.count(s2)) mp[s2]=++len; B[i]=mp[s2]; } cin>>n3; for(i=1;i<=n3;i++){ cin>>s>>s2; if(!mp.count(s)) mp[s]=++len; if(!mp.count(s2)) mp[s2]=++len; aa[mp[s]][mp[s2]]=1; } S=0,T=len+1; for(int k=1;k<=len;k++) for(i=1;i<=len;i++) for(j=1;j<=len;j++) aa[i][j]|= aa[i][k]&&aa[k][j]; for(i=1;i<=len;i++) for(j=1;j<=len;j++) if(i!=j&&aa[i][j]) add_(i,j,inf); for(i=1;i<=n1;i++) add_(A[i],T,1); for(i=1;i<=n2;i++) add_(S,B[i],1); int ans=0; while(bfs()) ans+=dfs(S,inf); cout<< n2-ans <<endl; if(cas) cout<<endl; } signed main(){ int tes; cin>>tes; while(tes--) sov(tes); }
标签:Plug,int,s2,len,UNIX,mp,uva,hd,dis From: https://www.cnblogs.com/towboa/p/17316342.html