（队长）最大流 预流推进.txt

ACM资料大集合

/*
  Name:         PKU 1273 Drainage Ditches 
  Alg:          Generic Preflow Push O(EV^2)
  Author:       Xiang Shuo
  Date: 21-07-07 20:09
  Description: 
*/
#include "cstdio"
#include "cstring"

using namespace std;

const int N = 210;
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;
    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;
                        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;
                }
                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;
}