网络流24题之一最大匹配
我用的还是最原始的EK算法,建图也比较简单,只要某两个人能配合好就给一个权值为1的边,然后增加一个超级源点和汇点,剩下的就是最大流了.不过最后输出时注意下(输出配对关系的时候),比如下面这组数据
2 4
1 3
1 4
2 3
-1 -1
代码如下:
/
LANG:C
TASK:
ID:qcx97811
/
#include
#include
#include
int graph[106][106],pre[106];
int N,M,maxflow
int bfs()
{
int i,j
int q[206];
int front,rear
memset(pre,-1,sizeof(pre));
front = rear = -1
q[++rear] = 0
while(front < rear)
{
i = q[++front];
for(j = 0j <= (N+1);j++)
{
if(-1 == pre[j] & graph[i][j] > 0)
{
pre[j] = i
rear++
q[rear] = j
if(j == (N+1))
return 1
}
}
}
return 0
}
void max_flow()
{
int i,j,add
maxflow = 0
while(0 != (add = bfs()))
{
add = 10000006
for(i = (N+1);i != 0i = pre[i])
{
j = pre[i];
if(graph[j][i] < add)
add = graph[j][i];
}
for(i = (N+1);i != 0i = pre[i])
{
j = pre[i];
graph[j][i] -= add
graph[i][j] += add
}
maxflow += add
}
}
int main(void)
{
freopen(“24-1.in”,“r”,stdin);
freopen(“24-1.out”,“w”,stdout);
int i,j,s,e
scanf(“%d%d”,M,&N);
memset(graph,0,sizeof(graph));
while(1)
{
scanf(“%d%d”,s,&e);
if((-1 == s) & (-1 == e))
break
if(s > e)
{//确定是从一个方向流往另外一个方向
i = s;
s = e
e = i
}
graph[s][e] = 1
}
for(i = 1i <= M;i++)//超级源点
graph[0][i] = 1
for(i = M+1i <= N;i++)//超级汇点
graph[i][N+1] = 1
max_flow();
if(0 == maxflow)
{
printf(“No Solution\n“);
}
else
{
printf(“%d\n“,maxflow);
for(i = 1i <= M;i++)
{
for(j = (M+1);j <= N;j++)
{
if(graph[j][i] == 1)
{
printf(“%d %d\n“,i,j);
//这里的输出注意下 附数据如下
//2 4
//1 3
//1 4
//2 3
//-1 -1
}
}
}
}
return 0
}
LANG:C
TASK:
ID:qcx97811
/
#include
#include
#include
int graph[106][106],pre[106];
int N,M,maxflow
int bfs()
{
int i,j
int q[206];
int front,rear
memset(pre,-1,sizeof(pre));
front = rear = -1
q[++rear] = 0
while(front < rear)
{
i = q[++front];
for(j = 0j <= (N+1);j++)
{
if(-1 == pre[j] & graph[i][j] > 0)
{
pre[j] = i
rear++
q[rear] = j
if(j == (N+1))
return 1
}
}
}
return 0
}
void max_flow()
{
int i,j,add
maxflow = 0
while(0 != (add = bfs()))
{
add = 10000006
for(i = (N+1);i != 0i = pre[i])
{
j = pre[i];
if(graph[j][i] < add)
add = graph[j][i];
}
for(i = (N+1);i != 0i = pre[i])
{
j = pre[i];
graph[j][i] -= add
graph[i][j] += add
}
maxflow += add
}
}
int main(void)
{
freopen(“24-1.in”,“r”,stdin);
freopen(“24-1.out”,“w”,stdout);
int i,j,s,e
scanf(“%d%d”,M,&N);
memset(graph,0,sizeof(graph));
while(1)
{
scanf(“%d%d”,s,&e);
if((-1 == s) & (-1 == e))
break
if(s > e)
{//确定是从一个方向流往另外一个方向
i = s;
s = e
e = i
}
graph[s][e] = 1
}
for(i = 1i <= M;i++)//超级源点
graph[0][i] = 1
for(i = M+1i <= N;i++)//超级汇点
graph[i][N+1] = 1
max_flow();
if(0 == maxflow)
{
printf(“No Solution\n“);
}
else
{
printf(“%d\n“,maxflow);
for(i = 1i <= M;i++)
{
for(j = (M+1);j <= N;j++)
{
if(graph[j][i] == 1)
{
printf(“%d %d\n“,i,j);
//这里的输出注意下 附数据如下
//2 4
//1 3
//1 4
//2 3
//-1 -1
}
}
}
}
return 0
}
