程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA - 1161 Objective: Berlin(最大流＋時序模型)

UVA - 1161 Objective: Berlin(最大流＋時序模型)

編輯：C++入門知識

UVA - 1161 Objective: Berlin(最大流＋時序模型)

題目大意：有n個城市m條航線，給出每條航線的出發地，目的地，座位數，起飛時間和到達時間(所給形式為HHMM，記得轉化)，再給出城市A和B，和到達城市B的最晚時間，現在問一天內最多有多少人能從A飛到B，可以在其他城市中轉

解題思路：將飛機票拆點，拆成i–>i ＋ m,容量為座位數。
接著判斷一下，航線之間的連線
如果航線的起點是A的話，那麼就和超級源點相連，容量為INF
如果航線的終點是B且到達時間小於等於最晚時間，那麼連線，容量為INF
如果航線i的終點和航線j的起點相同，且航線i的到達時間+30<=航線j的起始時間，那麼連線，容量為INF

#include 
#include 
#include 
#include 
#include 
#include
#include 
using namespace std;
#define N 10010
#define INF 0x3f3f3f3f

struct Edge{
    int from, to, cap, flow;
    Edge() {}
    Edge(int from, int to, int cap, int flow) : from(from), to(to), cap(cap), flow(flow) {}
};

struct Dinic{
    int n, m, s, t;
    vector edges;
    vector G[N];
    bool vis[N];
    int d[N], cur[N];

    void init(int n) {
        this->n = n;
        for (int i = 0; i <= n; i++) {
            G[i].clear();
        }
        edges.clear();
    }

    void AddEdge(int from, int to, int cap) {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        int m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    } 

    bool BFS() {
        memset(vis, 0, sizeof(vis));
        queue Q;
        Q.push(s);
        vis[s] = 1;
        d[s] = 0;

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for (int i = 0; i < G[u].size(); i++) {
                Edge &e = edges[G[u][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = true;
                    d[e.to] = d[u] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x, int a) {
        if (x == t || a == 0)
            return a;

        int flow = 0, f;
        for (int i = cur[x]; i < G[x].size(); i++) {
            Edge &e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0)
                    break;
            }
        }
        return flow;
    }

    int Maxflow(int s, int t) {
        this->s = s; this->t = t;
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, INF);
        }
        return flow;
    }
};


Dinic dinic;
#define M 5100
#define S 160
int n, m, source, sink, Time;
int num[S];
map Map;
struct Node {
    int u, v, c, s, t;
}node[M];

int getTime(string T) {
    int a = (T[0] - '0') * 10 + (T[1] - '0');
    int b = (T[2] - '0') * 10 + (T[3] - '0');
    return a * 60 + b;
}

void solve() {
    Map.clear();
    int cnt = 3;
    string a, b, s, t;

    cin >> a >> b >> s >> m;
    Map[a] = 1; Map[b] = 2;
    Time = getTime(s);

    memset(num, 0, sizeof(num));
    source = 0; sink = 2 * m + 1;
    dinic.init(sink);

    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> node[i].c >> s >> t;

        if (!Map[a]) Map[a] = cnt++;
        if (!Map[b]) Map[b] = cnt++;

        node[i].u = Map[a]; 
        node[i].v = Map[b];
        node[i].s = getTime(s);
        node[i].t = getTime(t);

        num[node[i].u]++; num[node[i].v]++;
        dinic.AddEdge(i, i + m, node[i].c);
    }

    if (!num[1] || !num[2]) {
        printf(0
);
        return ;
    }

    for (int i = 1; i <= m; i++) {
        int u = node[i].u, v = node[i].v;
        if (u == 1) dinic.AddEdge(source, i, INF);
        if (v == 2 && node[i].t <= Time) dinic.AddEdge(i + m, sink, INF);

        for (int j = 1; j <= m; j++) {
            if (i == j) continue;
            if (v != node[j].u) continue;
            if (node[i].t + 30 <= node[j].s) dinic.AddEdge(i + m, j, INF);

        }
    }
    int ans = dinic.Maxflow(source, sink);
    printf(%d
, ans);
}

int main() {
    while (scanf(%d
, &n) != EOF)  solve();
    return 0;
}