实质:把多源,多汇网络,构造成单源单汇网络,同时置所有边的容量为1。
操作:(G=(X∪Y,E))
(1)增加一个源点s和一个汇点t;
(2)从s向集合X的每一个顶点引一条有向边,从集合Y的每一个顶点向t引一条有向边;
(3)将原图的每条边改为从集合X向集合Y的有向边;
(4)置每条边的容量为1;
代码中的函数参见最大流模板点击打开链接
代码:
//输入
int N,K;//N代表集合X的数目,K代表集合Y的数目
bool can[max_n][max_k];//集合X和集合Y的联系
void solve()
{
//0~N-1:X中元素的序号
//N~N+K-1:Y中元素的序号
int s=N+K,t=s+1;//新增源点和汇点
//源点向集合X连边
for(int i=0;i<N;i++)
add_edge(s,i,1);
//集合Y向汇点连边
for(int i=0;i<K;i++)
add_edge(N+i,t,1);
//集合X向集合Y连边
for(int i=0;i<N;i++)
for(int j=0;j<K;j++)
if(can[i][j])
add_edge(i,N+j,1);
printf("%d\n",max_flow(s,t));
}