P2762 space flight plan problem (minimum cut)

n experiments, each experiment can gain ai yuan. How many instruments are needed for each experiment

Buying each instrument has different costs, different experiments may be used, the same instrument is purchased only once for maximum benefit

Explanation:...........................................

Let's talk about the construction of metaphysics

From s to each experimental connection weight is the edge of instrument income

The cost of each instrument to the t-connection weight instrument

Side of INF between experiment and instrument

The answer is equal to the benefit of all experiments minus (maximum flow = minimum cut)

If there is an S - > t path at present, it means that your experiment is lack of a certain instrument.

Because the meaning of cutting off the instrument is to buy the instrument, so the cost will be reduced.

If you cut out the experiment, you obviously don't do it.

Then the output scheme also learned that if the current point does not reach dis = INF at the last bfs, it means that the edge weight to this point is reduced to 0, and the flow is full, and this point is cut.

Being cut off in this question means choosing to do experiments and buy instruments.

 

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, m, s, t, maxflow, cnt;
struct node {
    int to, nex, val;
}E[100005];
int head[105];
int cur[105];

void addedge(int x, int y, int va) {
    E[++cnt].to = y; E[cnt].nex = head[x]; head[x] = cnt; E[cnt].val = va;
    E[++cnt].to = x; E[cnt].nex = head[y]; head[y] = cnt; E[cnt].val = 0;
}

int dep[105];
int inque[105];
bool bfs() {
    for(int i = 1; i <= t; i++) dep[i] = INF, inque[i] = 0, cur[i] = head[i];
    queue<int> que;
    que.push(s);
    dep[s] = 0, inque[s] = 1;

    while(!que.empty()) {
        int u = que.front();
        que.pop();
        inque[u] = 0;

        for(int i = head[u]; i; i = E[i].nex) {
            int v = E[i].to;
            if(E[i].val && dep[v] > dep[u] + 1) {
                dep[v] = dep[u] + 1;
                if(!inque[v]) {
                    que.push(v);
                    inque[v] = 1;
                }
            }
        }
    }
    return dep[t] != INF;
}

int vis;
int dfs(int x, int flow) {
    if(x == t) {
        maxflow += flow;
        vis = 1;
        return flow;
    }

    int rflow = 0;
    int used = 0;
    for(int i = cur[x]; i; i = E[i].nex) {
        cur[x] = i;
        int v = E[i].to;
        if(E[i].val && dep[v] == dep[x] + 1) {
            if(rflow = dfs(v, min(flow - used, E[i].val))) {
                used += rflow;
                E[i].val -= rflow;
                E[i ^ 1].val += rflow;
                if(used == flow) break;
            }
        }
    }
    return used;
}

void dinic() {
    maxflow = 0;
    while(bfs()) {
        vis = 1;
        while(vis) {
            vis = 0;
            dfs(s, INF);
        }
    }
}

int p[55];
int c[55];
int ans[55];
int viss[55];
int ned[55][55];
char tools[10000];

int main() {
    int sum = 0;
    scanf("%d%d", &n, &m);
    s = n + m + 1;
    t = s + 1;
    cnt = 1;
    int ulen;

    for(int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
        sum += p[i];
        addedge(s, i, p[i]);

        memset(tools, 0, sizeof(tools));
        cin.getline(tools, 10000);
        ulen = 0;
        int num;
        while(sscanf(tools + ulen, "%d", &num) == 1) {
            ned[i][num] = 1;
            addedge(i, n + num, INF);

            if(num == 0) ulen++;
            else {
                while(num) {
                    num /= 10;
                    ulen++;
                }
            }
            ulen++;
        }

    }
    for(int i = 1; i <= m; i++) scanf("%d", &c[i]);
    for(int i = 1; i <= m; i++) addedge(n + i, t, c[i]);
    dinic();

    for(int i = 1; i <= m; i++) {
        for(int j = head[i + n]; j; j = E[j].nex) {
            int v = E[j].to;
            if(v == t) {
                if(E[j].val == 0) viss[i] = 1;
                break;
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        if(dep[i] != INF) printf("%d ", i);
    }
    puts("");

    for(int i = 1; i <= m; i++) {
        if(dep[i + n] != INF) printf("%d ", i);
    }
    puts("");
    printf("%d\n", sum - maxflow);
    return 0;
}

Keywords: PHP

Added by jaikar on Wed, 23 Oct 2019 22:18:18 +0300