HDU 1532 Drainage Ditches-최대 흐름(sap 알고리즘)

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1532
Drainage Ditches
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 18864 Accepted Submission(s): 8980
Problem Description
Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite clover patch. This means that the clover is covered by water for awhile and takes quite a long time to regrow. Thus, Farmer John has built a set of drainage ditches so that Bessie's clover patch is never covered in water. Instead, the water is drained to a nearby stream. Being an ace engineer, Farmer John has also installed regulators at the beginning of each ditch, so he can control at what rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transport per minute but also the exact layout of the ditches, which feed out of the pond and into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can be transported out of the pond and into the stream. For any given ditch, water flows in only one direction, but there might be a way that water can flow in a circle.

Input
The input includes several cases. For each case, the first line contains two space-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200). N is the number of ditches that Farmer John has dug. M is the number of intersections points for those ditches. Intersection 1 is the pond. Intersection point M is the stream. Each of the following N lines contains three integers, Si, Ei, and Ci. Si and Ei (1 <= Si, Ei <= M) designate the intersections between which this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0 <= Ci <= 10,000,000) is the maximum rate at which water will flow through the ditch.

Output
For each case, output a single integer, the maximum rate at which water may emptied from the pond.

Sample Input

 
   
     5 4 1 2 40 1 4 20 2 4 20 2 3 30 3 4 10

代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int mod = 1e9+7;
const int MAXN = 500+10;

struct Edge
{
    int to, next, cap, flow;
}edge[MAXN*MAXN];
int tot, head[MAXN];

int gap[MAXN], dep[MAXN], pre[MAXN], cur[MAXN];

void add(int u, int v, int w)
{
    edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = 0;
    edge[tot].next = head[u]; head[u] = tot++;
    
    edge[tot].to = u; edge[tot].cap = 0; edge[tot].flow = 0;
    edge[tot].next = head[v]; head[v] = tot++;
}

int sap(int start, int end, int n)
{
    memset(gap,0,sizeof(gap));
    memset(dep,0,sizeof(dep));
    memcpy(cur,head,sizeof(head));
    int u = start;
    pre[u] = -1;
    gap[0] = n;
    int maxflow = 0;
    while(dep[start]edge[i].cap-edge[i].flow)
                        minn = edge[i].cap-edge[i].flow;
                for(int i = pre[u]; i!=-1; i=pre[edge[i^1].to])
                {
                    edge[i].flow += minn;
                    edge[i^1].flow -= minn;
                }
                u = start;
                maxflow += minn;
            }
        }

        else
        {
            int minn = n;
            for(int i = head[u]; i!=-1; i=edge[i].next)
                if(edge[i].cap-edge[i].flow && dep[edge[i].to]

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

[네트워크 흐름 24문제] [codevs1906] 최장 증자 서열 (dp+isap)

전송문 제목의 bug:1、데이터 범위는 주지 않았지만 눈대중으로 아무렇게나 열면 돼요. 한 점을 두 점으로 나누어 각 점의 사용 횟수를 보증하다.관계의 전이 dp 이후 i가 j 이전에 만족해야 하며 i의 값이 j의 ...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

HDU 1532 Drainage Ditches-최대 흐름(sap 알고리즘)

좋은 웹페이지 즐겨찾기