讨论 / 大牛们,help,有问题请教呀!
xiongnanbin 2009-03-22 04:38:00
点我顶贴 收藏 删除
如下是本题的本人的AC代码,看到双斜线的哪个语句吗,我加也AC,没加也AC,把我给搞的晕晕的,请问大牛们这是什么原因,又是什么原理。

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

long c[51][51],fl1[51][51],queue[51],pre[51],n,ans,sumflow;

bool visit[51];

long find_minflow(long x,long y)

{

if (x>y) return y;

else return x;

}

void change_flow(long sink)

{

long minflow,i;

minflow=0xfffffff;

i=sink;

while (i!=1)

{

minflow=find_minflow(minflow,fl1[pre[i]][i]);

i=pre[i];

}

sumflow+=minflow;

i=sink;

while (i!=1)

{

fl1[pre[i]][i]-=minflow;

// fl1[i][pre[i]]+=minflow;

i=pre[i];

}

}

void find_flow(long sink)

{

long head,tail,start,i;

for (i=1;i<=n;i++)

{

pre[i]=0;

visit[i]=false;

}

head=tail=1;visit[1]=true;

queue[head]=1;

while (head<=tail)

{

start=queue[head];

for (i=1;i<=n;i++)

if (!visit[i] && fl1[start][i]>0)

{

visit[i]=true;

tail++;

queue[tail]=i;

pre[i]=start;

}

head++;

}

}

int main()

{

scanf("%d\n",&n);

char cc;

for (int i=1;i<=n;i++)

{

for (int j=1;j<=n;j++)

{

scanf("%c",&cc);

c[i][j]=cc-’0’;

}

getchar();

}

ans=0x7fffffff;

long k,i;

for (i=2;i<=n;i++)

{

k=i;sumflow=0;

memcpy(fl1,c,sizeof(long)*(51*51));

for (;;)

{

find_flow(k);

if (!visit[k]) break;

change_flow(k);

}

if (sumflow<ans) ans=sumflow;

}

printf("%d\n",ans);

return 0;

}

#1 hws_sheng@2009-03-22 04:38:00
回复 删除
fl1[pre[i]][i]-=minflow;

// fl1[i][pre[i]]+=minflow;

i=pre[i];

就是以上那句话 听说网络流是对有向图来言的,如果是无向图那应该???搞不懂

查看更多回复
提交回复