先缩点，然后拆点，其实是很经典的一种操作，把不好做的点拆成边，然后我一开始想的是网络流，答案当然是增广次数，
但可以发现跑网络流的话不同的跑法增广次数不一样，不太好找最小的。我们可以换一种神奇的思路，跑最大费用流，
这样根据费用流每次都在最长路上增广保证每次都跑了尽量多的点，根据贪心原理可知这样是正确的。
详见http://blog.csdn.net/iamzky/article/details/41846687；
（一开始我一直错，发现自己增广用的dinic，模板打惯了就直接打上了。。。。忘了dinic是可以一次dfs实现多次增广的，没法统计增广次数。。我好蠢啊）
#include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; const int maxn=100010,inf=1e9; struct edg{ int nxt,to,f,c; }e[maxn],g[maxn]; int res,last[maxn],H[maxn],t1=1,t2=1,cas,dis[maxn],q[maxn],head,tail; void add1(int x,int y){ ++t1;e[t1].nxt=last[x];last[x]=t1;e[t1].to=y; } void add2(int x,int y,int z,int zz){ ++t2;g[t2].nxt=H[x];H[x]=t2;g[t2].to=y;g[t2].f=z;g[t2].c=zz; ++t2;g[t2].nxt=H[y];H[y]=t2;g[t2].to=x;g[t2].f=0;g[t2].c=-zz; } int scc,low[maxn],dfn[maxn],bel[maxn],cnt,sta[maxn],top,in[maxn]; void tarjan(int x){ low[x]=dfn[x]=++cnt;sta[++top]=x;in[x]=1; for(int i=last[x];i;i=e[i].nxt){ int v=e[i].to; if(!dfn[v]){ tarjan(v);low[x]=min(low[x],low[v]); } else{ if(in[v])low[x]=min(low[x],dfn[v]); } } //cout<<"orz"<<endl; if(low[x]==dfn[x]){ int now=0;scc++; while(now!=x){ now=sta[top--];in[now]=0; bel[now]=scc; } } } struct dui{ int from,to; }tmp[maxn]; int pe[maxn],pv[maxn],mp[2010][2010],ans,vis[maxn],N,n,m,a,b,x,y,S,T,A[maxn],B[maxn],a1[maxn],b1[maxn]; void solve(){ while(1){ memset(dis,-1,sizeof(dis)); head=tail=0;q[++tail]=S;dis[S]=0;vis[S]=1; while(head!=tail){ head=(head+1)%maxn; int u=q[head]; for(int i=H[u];i;i=g[i].nxt){ int v=g[i].to; if(g[i].f&&dis[v]<dis[u]+g[i].c){ dis[v]=dis[u]+g[i].c; pe[v]=i;pv[v]=u; if(!vis[v]){ vis[v]=1;tail=(tail+1)%maxn; q[tail]=v; } } } vis[u]=0; } if(dis[T]<0)break; int mm=inf; for(int u=T;u!=S;u=pv[u]) mm=min(mm,g[pe[u]].f); for(int u=T;u!=S;u=pv[u]) g[pe[u]].f-=mm,g[pe[u]^1].f+=mm; res+=dis[T]*mm; if(dis[T]>0) ++ans; } } int main(){ cin>>cas; while(cas--){ memset(mp,0,sizeof(mp)); memset(last,0,sizeof(last)); memset(H,0,sizeof(H)); memset(dfn,0,sizeof(dfn)); cin>>n>>m>>a>>b; t1=t2=1;scc=cnt=0; for(int i=1;i<=a;++i){scanf("%d",&A[i]);} for(int i=1;i<=b;++i)scanf("%d",&B[i]); for(int i=1;i<=m;++i){ scanf("%d%d",&tmp[i].from,&tmp[i].to); add1(tmp[i].from,tmp[i].to); } for(int i=1;i<=n;++i){ if(!dfn[i])tarjan(i); } S=1;T=scc*2+2; for(int i=1;i<=n;++i){ for(int j=last[i];j;j=e[j].nxt){ int u=bel[i],v=bel[e[j].to]; if(mp[u][v]||u==v)continue; add2(u+scc+1,v+1,inf,0); mp[u][v]=mp[v][u]=1; } } for(int i=1;i<=a;++i){ add2(S,1+bel[A[i]],inf,0); } for(int i=1;i<=b;++i){ add2(1+bel[B[i]]+scc,T,inf,0); } for(int i=1;i<=scc;++i){ add2(1+i,1+scc+i,1,1);add2(1+i,1+scc+i,inf,0); } res=ans=0;solve(); if(res!=scc)puts("no solution"); else{printf("%d ",ans);} } //system("pause"); return 0; }