EK 68pts #TLE 求调
查看原帖
EK 68pts #TLE 求调
460020
mmr123楼主2023/12/17 19:45
#include <bits/stdc++.h>
using namespace std;

int read() {
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x  = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

struct line {
    int to, w, fb;
};

int n, m, s, t;
vector<line> mp[205];

bool inq[205];
struct Pre {
    int from, edge;
} pre[205];

bool zg() {

    queue<int> q;
    memset(inq, false, sizeof(inq));
    memset(pre, -1, sizeof(pre));

    inq[s] = 1;
    q.push(s);

    while (!q.empty()) {
        int now = q.front();
        q.pop();

        for (int i = 0; i < mp[now].size(); i++) {
            int v = mp[now][i].to;

            if (!inq[v] && mp[now][i].w) {
                pre[v].from = now;
                pre[v].edge = i;
                if (v == t) {
                    return true;
                }
                inq[v] = true;
                q.push(v);
            }
        }
    }

    return false;
}

int ek() {
    int ans = 0;
    while (zg()) {
        int mi = 0x3f;
        for (int i = t; i != s; i = pre[i].from) {
            mi = min(mi, mp[pre[i].from][pre[i].edge].w);
        }
        for (int i = t; i != s; i = pre[i].from) {
            mp[pre[i].from][pre[i].edge].w -= mi;
            mp[i][mp[pre[i].from][pre[i].edge].fb].w += mi;
        }
        ans += mi;
    }
    return ans;
}

int main() {

    // freopen("P3376.in", "r", stdin);
    // freopen("P3376.out", "w", stdout);

    cin >> n >> m >> s >> t;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        // cin >> u >> v >> w;
        u = read(), v = read(), w = read();

        mp[v].push_back({u, 0, int(mp[u].size())});
        mp[u].push_back({v, w, int(mp[v].size() - 1)});
    }

    cout << ek() << endl;

    // fclose(stdin);
    // fclose(stdout);

    // system("pause");

    return 0;
}

好像死循环了,求大佬帮助!!!!

2023/12/17 19:45
加载中...