网络流24题-3 最小路径覆盖
提交地址
首先是这题有提示,不然还真是很难想的啊.有了提示之后,只需要想清楚为什么这样的构图是正确的,正确性的证明在有了图之后还是很好证明的,可以形成一条一条的链,从左到右再到左,依此循环,知道某个点”没有出度”为止.这样之后就很容易看出最小路径覆盖的条数就是总点数-最大流.接下来就是输出路径了,我用的也是链一样的形式,从左边开始,在右边找一个点[这个点满足一开始两点之间有流量,现在流量为0]然后一直枚举左边没输出过的点就OK了.这里附上我的代码:这个sap代码有了基本的要注意的地方.
/
ID:qcx97811
LANG:C
TASK:24-3/NKU_2123
/
#include
#include
#include
#include
#include
int n,m
int graph[360][360],c[360][360];
int d[360],gap[360],maxflow
void sap()
{
int u,v
int q[360],low[360];//这里的数组大小是顶点的个数+i
int tmp,front,rear
maxflow=0
//bfs
q[rear=0]=n2+1//这里是汇点
front=-1
memset(d,-1,sizeof(d));
memset(gap,0,sizeof(gap));
d[2n+1]=0//这里是汇点的层次度为0
while(front < rear)
{
u=q[++front];
for(v=0v<=2n+1;v++)//这里注意 上界是顶点的最大下标 下界是最小下标
{
if((-1==d[v])&(graph[v][u]>0))
{//这里是graph[v][u]不是graph[u][v]!!!
q[++rear]=v
d[v] = d[u]+1
gap[d[v]]++
}
}
}
//sap
q[tmp=0]=0//这里是起点
low[0]=INT_MAX//这里记得赋值 无穷大
while(d[0]<2(1+n))//这里的2(n+1)是如果所有的点是一条链的时候源点的标号+1
{//这里是起点的层次信息
u=q[tmp];
for(v=0v<=2n+1;v++)//这里的n2+1是顶点的最大标号
{
if(graph[u][v]>0 & d[v]+1==d[u])
break
}
if(2(n+1)==v)//这里v==上面for循环的上界+1
{//此点出度为0
gap[d[u]]–
if(gap[d[u]] == 0)
break
d[u]=2n+2//这里应该赋值为一个无穷大
for(v=0v<=2n+1;v++)//这里的n2+1是顶点的最大标号
{
if(graph[u][v] > 0 & d[v] >=0 && d[v]+1<d[u])
d[u]=d[v]+1
}
gap[d[u]]++
if(tmp>0)
tmp–
}
else
{
q[++tmp]=v
low[tmp]=graph[u][v];
if(low[tmp-1]<low[tmp])
low[tmp]=low[tmp-1];
if(v==2n+1)//这里的n2+1是顶点的最大标号
{//找到一条增广路
maxflow+=low[tmp];
for(u=0u<tmp;u++)
{//改变残留网络
front = q[u];
rear = q[u+1];
graph[front][rear] -= low[tmp];
graph[rear][front] += low[tmp];
}
tmp=0
}
}
}
}
void output()
{
char used[360];
int i,j,now
memset(used,0,sizeof(used));
for(i=1i<=n;i++)
{
if(0==used[i])
{
printf(“%d”,i);
now=i
while(1)
{
used[now]=1
for(j=1j<=c[now][0];j++)
{
if(0==used[c[now][j]]&0==graph[now][c[now][j]])
{
printf(“ %d”,c[now][j]-n);
used[c[now][j]]=1
break
}
}
if(c[now][0]+1==j)
break
else
now=c[now][j]-n;
if(1==used[now])
break
}
printf(“\n“);
}
}
printf(“%d\n“,n-maxflow);
}
int main(void)
{
freopen(“24-3.in”,“r”,stdin);
freopen(“24-3.out”,“w”,stdout);
int i,s,e,j
scanf(“%d%d”,n,&m);
memset(graph,0,sizeof(graph));
memset(c,0,sizeof(c));
for(i=0i<m;i++)
{
scanf(“%d%d”,s,&e);
graph[s][n+e]=1
c[s][++c[s][0]]=n+e
}
for(i=1i<=n;i++)
{
graph[0][i]=1
graph[n+i][2n+1]=1
}
#if 0
for(i=0;i<2*(n+1);i++)< span="">
{
for(j=0;j<2*(n+1);j++)< span="">
printf(“(%d,%d:%d) “,i,j,graph[i][j]);
printf(“\n”);
}
#endif
#if 1
sap();
output();
#endif
return 0
}
ID:qcx97811
LANG:C
TASK:24-3/NKU_2123
/
#include
#include
#include
#include
#include
int n,m
int graph[360][360],c[360][360];
int d[360],gap[360],maxflow
void sap()
{
int u,v
int q[360],low[360];//这里的数组大小是顶点的个数+i
int tmp,front,rear
maxflow=0
//bfs
q[rear=0]=n2+1//这里是汇点
front=-1
memset(d,-1,sizeof(d));
memset(gap,0,sizeof(gap));
d[2n+1]=0//这里是汇点的层次度为0
while(front < rear)
{
u=q[++front];
for(v=0v<=2n+1;v++)//这里注意 上界是顶点的最大下标 下界是最小下标
{
if((-1==d[v])&(graph[v][u]>0))
{//这里是graph[v][u]不是graph[u][v]!!!
q[++rear]=v
d[v] = d[u]+1
gap[d[v]]++
}
}
}
//sap
q[tmp=0]=0//这里是起点
low[0]=INT_MAX//这里记得赋值 无穷大
while(d[0]<2(1+n))//这里的2(n+1)是如果所有的点是一条链的时候源点的标号+1
{//这里是起点的层次信息
u=q[tmp];
for(v=0v<=2n+1;v++)//这里的n2+1是顶点的最大标号
{
if(graph[u][v]>0 & d[v]+1==d[u])
break
}
if(2(n+1)==v)//这里v==上面for循环的上界+1
{//此点出度为0
gap[d[u]]–
if(gap[d[u]] == 0)
break
d[u]=2n+2//这里应该赋值为一个无穷大
for(v=0v<=2n+1;v++)//这里的n2+1是顶点的最大标号
{
if(graph[u][v] > 0 & d[v] >=0 && d[v]+1<d[u])
d[u]=d[v]+1
}
gap[d[u]]++
if(tmp>0)
tmp–
}
else
{
q[++tmp]=v
low[tmp]=graph[u][v];
if(low[tmp-1]<low[tmp])
low[tmp]=low[tmp-1];
if(v==2n+1)//这里的n2+1是顶点的最大标号
{//找到一条增广路
maxflow+=low[tmp];
for(u=0u<tmp;u++)
{//改变残留网络
front = q[u];
rear = q[u+1];
graph[front][rear] -= low[tmp];
graph[rear][front] += low[tmp];
}
tmp=0
}
}
}
}
void output()
{
char used[360];
int i,j,now
memset(used,0,sizeof(used));
for(i=1i<=n;i++)
{
if(0==used[i])
{
printf(“%d”,i);
now=i
while(1)
{
used[now]=1
for(j=1j<=c[now][0];j++)
{
if(0==used[c[now][j]]&0==graph[now][c[now][j]])
{
printf(“ %d”,c[now][j]-n);
used[c[now][j]]=1
break
}
}
if(c[now][0]+1==j)
break
else
now=c[now][j]-n;
if(1==used[now])
break
}
printf(“\n“);
}
}
printf(“%d\n“,n-maxflow);
}
int main(void)
{
freopen(“24-3.in”,“r”,stdin);
freopen(“24-3.out”,“w”,stdout);
int i,s,e,j
scanf(“%d%d”,n,&m);
memset(graph,0,sizeof(graph));
memset(c,0,sizeof(c));
for(i=0i<m;i++)
{
scanf(“%d%d”,s,&e);
graph[s][n+e]=1
c[s][++c[s][0]]=n+e
}
for(i=1i<=n;i++)
{
graph[0][i]=1
graph[n+i][2n+1]=1
}
#if 0
for(i=0;i<2*(n+1);i++)< span="">
{
for(j=0;j<2*(n+1);j++)< span="">
printf(“(%d,%d:%d) “,i,j,graph[i][j]);
printf(“\n”);
}
#endif
#if 1
sap();
output();
#endif
return 0
}
