您當(dāng)前位置：首頁 > php開源 > 綜合技術(shù) > poj逗比了...

poj逗比了...

來源：程序員人生發(fā)布時(shí)間：2015-05-11 08:31:55 閱讀次數(shù)：3560次

首先，這是1個(gè)TextArea的bug，真的仿佛是1個(gè)bug

只需要在poj1459中提交以下代碼，就會發(fā)現(xiàn)，，，它其實(shí)提交不了…

#include <cstdio>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 107;
const int INF = 0xfffffff;
struct node {
    int to;
    int cap;
    int rev;
};
vector<node> G[MAX];
int level[MAX];
bool vis[MAX];
int n, np, nc, m, S, T;

inline void add_edge(int u, int v, int c) {
    G[u].push_back((node){v, c, G[v].size()});
    G[v].push_back((node){u, 0, G[u].size() - 1});
}

bool BFS(int S, int T) {
    queue<int> Q;
    Q.push(S);
    memset(level, -1, sizeof(level));
    level[S] = 0;
    while (!Q.empty()) {
        int p = Q.front();
        Q.pop();
        for (vector<node>::iterator it = G[p].begin(); it != G[p].end(); ++it) {
            if (level[it->to] < 0 && it->cap > 0) {
                level[it->to] = level[p] + 1;
                Q.push(it->to);
                if (it->to == T) return true;
            }
        }
    }
    return false;
}

int DFS(int u, int v, int c) {
    if (u == v) return c;
    int sum = 0, tmp;
    for (vector<node>::iterator it = G[u].begin(); it != G[u].end(); ++it) {
        if (level[it->to] == level[u] + 1 && it->cap > 0) {
            tmp = DFS(it->to, T, min(c - sum, it->cap));
            sum += tmp;
            it->cap -= tmp;
            G[it->to][it->rev].cap += tmp;
        }
    }
    return sum;
}

// from S to T, with max cap: C
int dinic(int S, int T) {
    int sum = 0;
    while (BFS(S, T)) {
        memset(vis, false, sizeof(vis));
        sum += DFS(S, T, INF);
    }
    return sum;
}

int main() {
    while (~scanf(" %d %d %d %d", &n, &np, &nc, &m)) {
        S = n, T = n + 1;
        for (int i = 0; i <= T; ++i) G[i].clear();
        int a, b, c;
        for (int i = 0; i < m; ++i) {
            scanf(" (%d,%d)%d", &a, &b, &c);
            add_edge(a, b, c);
        }
        for (int i = 0; i < np; ++i) {
            scanf(" (%d)%d", &a, &c);
            add_edge(S, a, c);
        }
        for (int i = 0; i < nc; ++i) {
            scanf(" (%d)%d", &a, &c);
            add_edge(a, T, c);
        }

        printf("%d
", dinic(S, T));
    }

    return 0;
}