您当前位置：首页 > php开源 > 综合技术 > poj逗比了...

poj逗比了...

来源：程序员人生发布时间：2015-05-11 08:31:55 阅读次数：3412次

首先，这是1个TextArea的bug，真的仿佛是1个bug

只需要在poj1459中提交以下代码，就会发现，，，它其实提交不了…

#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;
}

但是，但是，但是，如果删了这句注释：

// from S to T, with max cap:

或只是移到其它位置，就没有丝毫问题!

那末问题来了，这是怎样回事？！

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 判断一本书是否为好书的方法

下一篇 ios UI数据库 sqlite小型数据库的增、删、改、查、排序

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点