题目大意
给出一个有向图，指定一些起点与终点，询问从指定起点与终点的所有路径中选出最少多少路径可以覆盖原图。
题目分析
显然若到达一个边双连通分量中任意一点，内部所有点均可以到达。
因此直接将边双连通分量缩点。
剩下的是一个可重复经过点，带有起终点限制的最小路径覆盖问题。
带限制可以采用流量平衡模型进行解决。
引一个超级源点，不断加流，直到不能更新答案为止。
最小路径覆盖可以在上述流量平衡基础上通过费用来统计被覆盖的点数。
先按照普通的二分图建图，然后给每个入点到出点加两条边，一条容量为$1$，费用为$1$，一条容量$inf$，费用为$0$，表示每个点只能给被覆盖的点数贡献一次。
需要注意的是，原图上的边要反着建，也就是说从出点到入点建边。原因是要和流量平衡模型兼容。
代码
我的代码常数大，太慢了，bzoj过不了。
黄学长的费用流很快啊，大家可以去看hzwer的题解啦。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
inline int min(int a,int b) {
if(a<b)return a;
return b;
}
struct Edge {
int from,to,cap,flow,cost;
Edge(int x=0,int y=0,int c=0,int f=0,int co=0):from(x),to(y),cap(c),flow(f),cost(co) {}
};
struct zkw_CostFlow {
const static int maxn=2010;
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool inque[maxn],vst[maxn];
int dist[maxn],cur[maxn];
int flow,cost;
void init(int n) {
this->n=n;
flow=cost=0;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
int AddEdge(int x,int y,int v,int f) {
edges.push_back(Edge(x,y,v,0,f));
edges.push_back(Edge(y,x,0,0,-f));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
return m-2;
}
bool spfa() {
for(int i=1; i<=n; i++)dist[i]=-INT_MAX,inque[i]=0;
dist[t]=0;
inque[t]=1;
deque<int>Q;
Q.push_back(t);
while(!Q.empty()) {
int Now=Q.front();
Q.pop_front();
inque[Now]=0;
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(dist[Next]<dist[Now]+e.cost&&e.cap>e.flow) {
dist[Next]=dist[Now]+e.cost;
if(!inque[Next]) {
inque[Next]=1;
if(!Q.empty()&&dist[Next]>dist[Q.front()])Q.push_front(Next);
else Q.push_back(Next);
}
}
}
}
return dist[s]>-INT_MAX;
}
int dfs(int Now,int a) {
if(vst[Now])return 0;
if(Now==t||a==0)return a;
int flow=0;
vst[Now]=1;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
int id=G[Now][i];
Edge& e=edges[id];
int Next=e.to;
if(dist[Now]-e.cost!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
cost+=nextflow*e.cost;
e.flow+=nextflow;
edges[id^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
while(spfa()) {
memset(vst,0,sizeof(vst));
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} zkw;
const int maxn=1007;
int t,n,m,a,b,step=0,top=0,BCC=0,Start[maxn],End[maxn],Belong[maxn],Dfn[maxn],Lowlink[maxn],Stack[maxn],Instack[maxn],Hash[maxn][maxn];
vector<int> edges[maxn];
void AddEdge(int x,int y) {
edges[x].push_back(y);
}
void Tarjan(int Now) {
Dfn[Now]=Lowlink[Now]=++step;
Stack[++top]=Now;
Instack[Now]=1;
for(int Next:edges[Now]) {
if(!Dfn[Next]) {
Tarjan(Next);
Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);
} else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
}
if(Dfn[Now]==Lowlink[Now]) {
BCC++;
int y;
do {
y=Stack[top--];
Instack[y]=0;
Belong[y]=BCC;
} while(y!=Now);
}
}
void Clear() {
for(int i=1; i<=n; i++)edges[i].clear();
memset(Dfn,0,sizeof(Dfn));
memset(Hash,0,sizeof(Hash));
step=BCC=0;
}
int main() {
t=Get_Int();
while(t--) {
n=Get_Int();
m=Get_Int();
a=Get_Int();
b=Get_Int();
Clear();
for(int i=1; i<=a; i++)Start[i]=Get_Int();
for(int i=1; i<=b; i++)End[i]=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int();
AddEdge(x,y);
}
for(int i=1; i<=n; i++)
if(!Dfn[i])Tarjan(i);
int fakeS=2*BCC+1,T=2*BCC+2,realS=T+1;
zkw.init(realS);
for(int i=1; i<=a; i++)zkw.AddEdge(fakeS,Belong[Start[i]],INT_MAX/2,0);
for(int i=1; i<=b; i++)zkw.AddEdge(BCC+Belong[End[i]],T,INT_MAX/2,0);
for(int i=1; i<=BCC; i++) {
zkw.AddEdge(i,BCC+i,1,1);
zkw.AddEdge(i,BCC+i,INT_MAX/2,0);
}
for(int Now=1; Now<=n; Now++)
for(auto Next:edges[Now]) {
if(Belong[Now]==Belong[Next]||Hash[Belong[Now]][Belong[Next]])continue;
zkw.AddEdge(BCC+Belong[Now],Belong[Next],INT_MAX/2,0);
}
int pre=0,ans=0;
int link=zkw.AddEdge(realS,fakeS,0,0);
do {
pre=zkw.cost;
zkw.edges[link].cap++;
zkw.maxflow(realS,T);
ans++;
} while(zkw.cost!=pre);
if(zkw.cost!=BCC)puts("no solution");
else printf("%d\n",ans-1);
}
return 0;
}
