最大流 预留推进(my).txt

NUAA ACM OJ源码

//网络最大流 预留推进法
/*
例子1：
输入：
4 5 1 4
1 2 6
1 3 4
2 3 3
2 4 4
3 4 8

输出：
10
 
例子2：
输入：
4 5 1 4
1 2 7
1 3 2
2 3 3
2 4 1
3 4 5

输出：
6

*/

#include <iostream>
#include <stdio.h>
using namespace std;

#define NMAX 7
#define MAX 100
int f[NMAX][NMAX];//点到点的流量限制
int e[NMAX];//点的盈余
int flow[NMAX][NMAX];//点到点的流量


int cal(int start,int end,int num)
{
	int i,j,tmin,tt;
	int flag,has;
	for(i=0;i<=num;i++)
	{
		e[i]=h[i]=0;
		for(j=1;j<=num;j++)
			f[i][j]=0;
	}
//	memset(e,0,sizeof(e));
//	memset(f,0,sizeof(flow));
//	memset(h,0,sizeof(h));
	for(i=0;i<=num;i++)
	{
		if(c[start][i]>0)
		{	//从源点往邻点推流
			e[start]-=c[start][i];
			e[i]+=c[start][i];
			f[start][i]+=c[start][i];
			f[i][start]-=c[start][i];
		}
	}
	flag=true;has=false;
	h[start]=num;//置源点高度
	while(flag == true)
	{
		flag=false;
		for(i=1;i<=num;i++)
		{
			if(e[i]>0&&i!=end)//注意i不能取end
			{	//i点有盈余
				flag=true;tmin=MAX*MAX;has=false;
				for(j=1;j<=num;j++)
				{
					if(c[i][j]>f[i][j])
					{	//从i点到j点理论上可推流
						if(h[i]==h[j]+1)
						{
							//当且仅当i点比j点高度高1，才可推流
							has=true;//推流了
							//特别说明:若f[i][j]=0,flow[i][j]为负数，为退流
							if(e[i]>c[i][j]-f[i][j]) tt=c[i][j]-f[i][j];
							else tt=e[i];
							e[i]-=tt;
							e[j]+=tt;
							f[i][j]+=tt;
							f[j][i]-=tt;
						}
						else
						{	//高度不合适
							if(tmin>h[j]+1) tmin=h[j]+1;
						}
					}
				}
				if(has==false) h[i]=tmin;//i点虽有盈余，但不可推流，则修改高度
			}
		}
	}
	return e[end];
}


int main()
{
	int num,i,pnum,ta,tb,tc;
	scanf("%d%d",&num,&pnum,&start,&end);
	for(i=0;i<pnum;i++)
	{
		scanf("%d%d%d",&ta,&tb,&tc);
		f[ta][tb]+=tc;
	}
	cout<<cal(num,start,end)<<endl;
	return 0;
}




/*

//author:xiang shuo
#include "cstdio"
#include "cstring"
#include "iostream"

using namespace std;

const int N = 6;
const int INF = 10000000;

int ad[N][N],flow[N][N];
int e[N],h[N];
int m,n;

int PreflowPush(int ad[N][N],int src,int des)
{
    int i,j,minh,t;
    bool has,flag;
    
    memset(e,0,sizeof(e));
    memset(h,0,sizeof(h));
    for(i=2;i<=n;i++)
    {
        e[i] += ad[src][i];
        e[src ] -= ad[src][i];
        flow[src][i] += e[i];
        flow[i][src] = -flow[src][i];
    }
    
    h[src] = n; flag = true;
    while(flag)
    {
        flag = false;
        for( i = 1; i < n; i++)
        {
            if(e[i] > 0)
            {
                flag = true; minh = INF; has = false;
                for( j = 1; j <= n; j++)
                {
                    if(ad[i][j] > flow[i][j] && h[i] == h[j] + 1)
                    {
                        has = true;
						if(e[i]<ad[i][j]-flow[i][j]) t=e[i];
						else t=ad[i][j]-flow[i][j];
        //                int t = e[i] <? ad[i][j] - flow[i][j];
                        e[i] -= t; 
                        e[j] += t;
                        flow[i][j] += t; 
                        flow[j][i] -= t;
                    }
   //               else if(ad[i][j] > flow[i][j]) minh <?= h[j] + 1;
					else if(ad[i][j] > flow[i][j])
					{
						if(minh>h[j]+1) minh=h[j]+1;
					}
                }
                if(!has) h[i] = minh;
            }
        }
    }
    return e[des];
} 

int main()
{
    int i,j,k;
		
//	int a,b;
//	a=a>b?b:a;


    while(scanf("%d%d",&m,&n)==2)
    {
        memset(ad,0,sizeof(ad));
        memset(flow,0,sizeof(flow));
        
        for(; m; m--)
        {
            scanf("%d%d%d",&i,&j,&k);
            ad[i][j] += k;
        }
        printf("%d\n",PreflowPush(ad,1,n));
    }
    return 0;
}
*/