一大牛的 网络最大流 程序(POJ 1273 )

和自己的比起来,感觉大牛的代码要精悍的多啊。
代码如下:
#include <stdio.h>
#include <string.h>
#define maxn 250
struct Map
{
 int f;
 int c;
}map[maxn][maxn];
int pre[maxn];
int q[maxn*maxn];
int v[maxn];
int N,M;
int s,t;
int abs( int x ){ return x > 0 ? x : -x ; }
int min( int x, int y ){ return  x < y ? x : y; }
void init()
{
 int i, S, E, C;
 memset( map, 0, sizeof(map) );
 for(i=0;i<N;i++)
 {
  scanf( "%d%d%d", &S, &E, &C );
  map[S][E].c += C;
 } 
}
void solve()
{
 int i,j;
 int head,tail;
 s = 1;
 t = M;
 while(true)
 {
  memset( pre, 0, sizeof(pre) );
  head = 0, tail = 1;
  q[0] = s;
  v[s] = 1000000000;
  pre[s] = s;
  while( head < tail && pre[t] == 0 )
  {
   i = q[head];
   for( j = 1; j <= M; j++ )
   {
    if( pre[j] == 0 )
    {
     if( map[i][j].f < map[i][j].c )
      pre[j] = i , q[tail++] = j , v[j] = min( v[i], map[i][j].c-map[i][j].f );
     else if( map[j][i].f > 0 )
      pre[j] = -i, q[tail++] = j , v[j] = min( v[i], map[j][i].f );
    }
            }
   head++;
  }
  if( pre[t] == 0 )break;

  i = t;
  while( i != s )
  {
   j = abs( pre[i] );
   if( pre[i] > 0 )map[j][i].f += v[t];
   else map[i][j].f -= v[t];
   i = j;
  }
 }
 int ans = 0;
 for( i = 1; i <= M; i++ )ans += map[s][i].f;
 printf("%d\n",ans);
}
int main()
{
 while(scanf("%d%d",&N,&M)!=EOF)
 {
  init();
  solve();
 }
 return 0;
}

posted on 2007-03-28 18:52 Barracuda 阅读(2591) 评论(6)  编辑 收藏 引用

评论

# re: 一大牛的 网络最大流 程序(POJ 1273 ) 2007-04-12 17:04 scnu_xiaokun

请问反向弧什么时候才会大于0,反弧的f初始化时肯定为0,只有当反向弧的权大于0时才会对反向弧进行处理,但它一开始老是为0了。急。。。  回复  更多评论   

# re: 一大牛的 网络最大流 程序(POJ 1273 ) 2007-04-12 17:15 scnu_xiaokun

能不能给组数据,谢谢  回复  更多评论   

# re: 一大牛的 网络最大流 程序(POJ 1273 ) 2007-04-13 23:09 whwangfei

找到一条路径后,找路径上最小权的边,然后正想边都减去这个最小权A,反向边加上这个最小权A,继续找路径,一直这样做直到找不到路径为着。累加A,就是最大流。  回复  更多评论   

# re: 一大牛的 网络最大流 程序(POJ 1273 ) 2008-07-29 11:16 vv

you wu   回复  更多评论   

# re: 一大牛的 网络最大流 程序(POJ 1273 ) 2008-07-31 16:30 ACMER

请问这叫什么算法?  回复  更多评论   

# re: 一大牛的 网络最大流 程序(POJ 1273 ) 2011-07-09 10:21 cucumber

额, 其实还是很罗嗦的嘛...  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2008年7月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿(1)

随笔档案

文章分类

搜索

最新评论

阅读排行榜

评论排行榜