您當前位置：首頁 > php開源 > php教程 > BZOJ 1570 JSOI 2008 Blue Mary的旅行網絡流

BZOJ 1570 JSOI 2008 Blue Mary的旅行網絡流

來源：程序員人生發布時間：2015-03-24 08:35:11 閱讀次數：2420次

題目大意

給出1個有向圖，每天每人只能做1次飛機。現在給出出發點，終點，和需要走的人數，還有每條航線的限制人數，問最少多少天最慢的人到達終點。

思路

很明顯是網絡流的模型，至于如何去驗證，其實連2分都不用，枚舉最少天數，然后每次加1層邊進行驗證就好了。

CODE

#define _CRT_SECURE_NO_WARNINGS

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 100010
#define MAXE 1000010
#define S 0
#define SS (MAX - 2)
#define T (MAX - 1)
#define INF 0x3f3f3f3f
using namespace std;

struct Edge{
    int x, y, z;

    void Read() {
        scanf("%d%d%d", &x, &y, &z);
    }
}edge[MAXE];

struct MaxFlow{
    int head[MAX], total;
    int _next[MAXE], aim[MAXE], flow[MAXE];
    int backup_flow[MAXE];
    int deep[MAXE];

    MaxFlow():total(1) {}
    void Add(int x, int y, int f) {
        _next[++total] = head[x];
        aim[total] = y;
        backup_flow[total] = f;
        head[x] = total;
    }
    void Insert(int x, int y, int f) {
        Add(x, y, f);
        Add(y, x, 0);
    }
    bool BFS() {
        static queue<int> q;
        while(!q.empty())   q.pop();
        memset(deep, 0, sizeof(deep));
        deep[S] = 1;
        q.push(S);
        while(!q.empty()) {
            int x = q.front(); q.pop();
            for(int i = head[x]; i; i = _next[i])
            if(flow[i] && !deep[aim[i]]) {
                deep[aim[i]] = deep[x] + 1;
                q.push(aim[i]);
                if(aim[i] == T) return true;
            }
        }
        return false;
    }
    int Dinic(int x, int f) {
        if(x == T)  return f;
        int temp = f;
        for(int i = head[x]; i; i = _next[i])
        if(flow[i] && temp && deep[aim[i]] == deep[x] + 1) {
            int away = Dinic(aim[i], min(flow[i], temp));
            if(!away)   deep[aim[i]] = 0;
            flow[i] -= away;
            flow[i ^ 1] += away;
            temp -= away;
        }
        return f - temp;
    }
}solver;

int points, edges, persons;

int main()
{
    cin >> points >> edges >> persons;
    for(int i = 1; i <= edges; ++i)
        edge[i].Read();
    solver.Insert(S, SS, persons);
    int now = 0;
    for(int i = 1;; ++i) {
        for(int j = 1; j <= edges; ++j)
            solver.Insert(now + edge[j].x, now + edge[j].y + points, edge[j].z);
        solver.Insert(now + points + points, T, INF);
        solver.Insert(SS, now + 1, INF);
        memcpy(solver.flow, solver.backup_flow, sizeof(solver.flow));
        int max_flow = 0;
        while(solver.BFS())
            max_flow += solver.Dinic(S, INF);
        if(max_flow == persons) {
            cout << i << endl;
            return 0;
        }
        now += points;
    }
    return 0;
}