pku 1459 最大流 SAP

比眉伴天荒 2021-11-01 13:28 649阅读 0赞

\#include  < iostream >   
\#include  < queue >   
 \#define  msize 205  // 最大顶点数目   
 // \#define INT\_MAX 100000000   
 using  namespace  std;  
 int  d\[msize\];  // 标号   
 int  r\[msize\]\[msize\];  // 残留网络，初始为原图   
 int  num\[msize\];  // num\[i\]表示标号为i的顶点数有多少   
 int  pre\[msize\];  
 int  n,m;  // m个顶点，n条边，从源点s到汇点t   
 int  min( int  a, int  b)  
\{  
 if (a < b)  return  a;  
 else  return  b;  
\}  
 void  init( int  s, int  t)  // BFS计算标号，汇点t标号为0   
 \{  
 int  k;  
queue < int > Q;  
memset(d, 1 , sizeof (d));  
memset(num, 0 , sizeof (num));  
Q.push(t);  
d\[t\] = 0 ;  
num\[ 0 \] = 1 ;  
 while  ( ! Q.empty())  
\{  
k = Q.front(),Q.pop();  
 for  ( int  i = 0 ;i < n \+ 2 ;i \++ )  
\{  
 if  (d\[i\] >= n \+ 2 && r\[i\]\[k\] > 0 )  
\{  
d\[i\] = d\[k\] \+ 1 ;  
Q.push(i);  
num\[d\[i\]\] \++ ;  
\}  
\}  
\}  
\}  
 int  findAlowArc( int  i)  // 从i出发寻找允许弧   
 \{  
 int  j;  
 for  (j = 0 ;j < n \+ 2 ;j \++ )  if  (r\[i\]\[j\] > 0 && d\[i\] == d\[j\] \+ 1 )  return  j;  
 return  \- 1 ;  
\}  
 int  reLable( int  i)  // 重新标号   
 \{  
 int  mm = INT\_MAX;  
 for  ( int  j = 0 ;j < n \+ 2 ;j \++ )  
 if  (r\[i\]\[j\] > 0 ) mm = min(mm,d\[j\] \+ 1 );  
  
 return  mm == INT\_MAX ? (n):mm;  
\}  
 int  maxFlow( int  s, int  t)  // 从源点s出发的最大流   
 \{  
 int  flow = 0 ,i = s,j;  
 int  delta;  // 增量   
  memset(pre, \- 1 , sizeof (pre));  
 while  (d\[s\] < n \+ 2 )  
\{  
j = findAlowArc(i);  
 if  (j >= 0 )  
\{  
pre\[j\] = i;  
i = j;  
 if  (i == t)  // 更新残留网络   
  \{  
delta = INT\_MAX;  
 for  (i = t;i != s;i = pre\[i\]) delta = min(delta,r\[pre\[i\]\]\[i\]);  
 for  (i = t;i != s;i = pre\[i\]) r\[pre\[i\]\]\[i\]  \-=  delta, r\[i\]\[pre\[i\]\]  \+=  delta;  
flow  \+=  delta;  
\}  
\}  
 else   
\{  
 int  x = reLable(i);  // 重新标号   
  num\[x\] \++ ;  
num\[d\[i\]\] \-- ;  
 if  (num\[d\[i\]\] == 0 )  return  flow;  // 间隙优化   
  d\[i\] = x;  
 if  (i != s) i = pre\[i\];  
\}  
\}  
 return  flow;  
\}  
 int  main()  
\{  
 int  i,j,k;  
 int  np,nc;  
 int  a,b,z;  
 while (scanf( " %d%d%d%d " , & n, & np, & nc, & m) != EOF)  
\{  
memset(r, 0 , sizeof (r));  
 for (i = 1 ;i <= m;i \++ )  
\{  
scanf( "  (%d,%d)%d " , & a, & b, & z);  
r\[a\]\[b\] = z;  
\}  
 for (i = 1 ;i <= np;i \++ )  
\{  
scanf( "  (%d)%d " , & a, & z);  
r\[n\]\[a\] = z;  
\}  
 for (i = 1 ;i <= nc;i \++ )  
\{  
scanf( "  (%d)%d " , & a, & z);  
r\[a\]\[n \+ 1 \] = z;  
\}  
init(n,n \+ 1 );  
printf( " %d\\n " ,maxFlow(n,n \+ 1 ));  
\}  
 return  0 ;  
\}

[http://blog.chinaunix.net/u3/102624/showart\_2064077.html][http_blog.chinaunix.net_u3_102624_showart_2064077.html]     参考模板

转载于:https://www.cnblogs.com/ACAC/archive/2010/05/18/1738742.html

[http_blog.chinaunix.net_u3_102624_showart_2064077.html]: http://blog.chinaunix.net/u3/102624/showart_2064077.html