传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2893
吐槽:为什么题目是征服王题面是wa2……而且我是冬马党……
而且上次提交是2013年5月……
这题……一眼缩点,缩成DAG,然后问题就是限制起点终点的可重复经过的最小路径覆盖
神奇的费用流:
对于一个点u,拆成u->u' ,连两条边,一条cap=1 cost=1,另一条cap=inf cost=0
s->u cap=inf cost=0,u' -> t cap=inf cost=0
对于原图的边<u,v>: u'->v cap=inf cost=0
跑最大费用流
有cost的边代表这个点经过一次
那么最大费用流每次会尽量走费用多的边,即走尽量多的点,正确性由网络流保证
增广次数即为答案
复杂度?
每次增广至少有1个cost,总共有n个cost,最坏增广n次
Code:
#include<bits/stdc++.h>
#undef INT_MAX
#define INT_MAX 100000
using namespace std;
const int maxn=1010;
int getint(){
int res=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))res=res*10+c-'0',c=getchar();
return res;
}
int n,m,a,b,ans=0;
vector<int>G[maxn];
namespace Flow{
const int maxn=2010;
int s=0,t=2009;
struct edge{
int u,v,cap,flow,cost;
edge(int _u=0,int _v=0,int _cap=0,int _flow=0,int _cost=0):
u(_u),v(_v),cap(_cap),flow(_flow),cost(_cost){}
};
vector<edge>edges;
vector<int>G[maxn];
int pre[maxn],a[maxn],d[maxn],vis[maxn],cost,flow;
void init(){
edges.clear();flow=cost=0;
for(int i=0;i<maxn;i++)G[i].clear();
}
void add(int u,int v,int cap,int cost){
edges.push_back(edge(u,v,cap,0,cost));
G[u].push_back(edges.size()-1);
edges.push_back(edge(v,u,0,0,-cost));
G[v].push_back(edges.size()-1);
}
bool spfa(){
queue<int>q;
q.push(s); vis[s]=1;
memset(d,-1,sizeof d);int B=d[0];d[s]=0;a[s]=INT_MAX;
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
for(int i=0;i<G[u].size();i++){
edge e=edges[G[u][i]];
if(e.cap>e.flow&&d[e.v]<d[u]+e.cost){
d[e.v]=d[u]+e.cost;
pre[e.v]=G[u][i];
a[e.v]=min(a[u],e.cap-e.flow);
if(!vis[e.v]){
vis[e.v]=1;
q.push(e.v);
}
}
}
}
if(d[t]==B)return false;
cost+=d[t]*a[t];
flow+=a[t];
for(int u=t;u!=s;u=edges[pre[u]].u){
edges[pre[u]].flow+=a[t];
edges[pre[u]^1].flow-=a[t];
}return d[t]>0;
}
void deb(){
for(int i=0;i<edges.size();i++)if(i%2==0)
printf("%d->%d cap:%d cost:%d\n",edges[i].u,edges[i].v,edges[i].cap,edges[i].cost);
}
}
int bel[maxn];
namespace SCC{
int cnt,dfn[maxn],low[maxn],tot;
stack<int>S;short ins[maxn];
void init(){
cnt=tot=0;
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(ins,0,sizeof ins);
memset(bel,0,sizeof bel);
}
void dfs(int u){
ins[u]=1;S.push(u);
dfn[u]=low[u]=++tot;
for(int i=0,v;i<G[u].size();i++){
if(!dfn[v=G[u][i]]){
dfs(v);
low[u]=min(low[u],low[v]);
}else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
cnt++;int v;
do{
v=S.top();S.pop();
bel[v]=cnt;
ins[v]=0;
}while(u!=v);
}
}
void tarjan(){
for(int i=1;i<=n;i++)if(!dfn[i])
dfs(i);
}
}
int st[maxn],ed[maxn],mp[maxn][maxn];
set<pair<int,int> >St;
void init(){
memset(mp,0,sizeof mp);
scanf("%d%d%d%d",&n,&m,&st[0],&ed[0]);
for(int i=1;i<=n;i++)G[i].clear();
for(int i=1;i<=st[0];i++)scanf("%d",&st[i]);
for(int i=1;i<=ed[0];i++)scanf("%d",&ed[i]);
for(int i=1;i<=m;i++){
int u,v;scanf("%d%d",&u,&v);
G[u].push_back(v);
}SCC::init();Flow::init();
}
void solve(){
SCC::tarjan();
for(int i=1;i<=SCC::cnt;i++)Flow::add(i<<1,i<<1|1,1,1),Flow::add(i<<1,i<<1|1,INT_MAX,0);
for(int i=1;i<=st[0];i++)Flow::add(Flow::s,bel[st[i]]<<1,INT_MAX,0);
for(int i=1;i<=ed[0];i++)Flow::add(bel[ed[i]]<<1|1,Flow::t,INT_MAX,0);
for(int i=1;i<=n;i++)for(int j=0;j<G[i].size();j++){
int u=bel[i],v=bel[G[i][j]];
if(mp[u][v]||u==v)continue;
Flow::add(u<<1|1,v<<1,INT_MAX,0);
mp[u][v]=mp[v][u]=1;
}ans=0;
//Flow::deb();
while(Flow::spfa())ans++;
if(Flow::cost!=SCC::cnt)puts("no solution");
else printf("%d\n",ans);
}
int main(){
int _=getint();
while(_--){
init();
solve();
}
return 0;
}