Участник:Taranov srg/Coconuts

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/COCONUTS

C++ 14 (clang 8.0)

 
#include<fstream>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1000000000;
 
struct Graph {
    int *c, *f, *ptr, *q, *d;
    int s, t, n;
 
    Graph (int _n, int _s, int _t, int* _c) {
        n = _n;
        s = _s;
        t = _t;
        c = _c;
        f = new int[n*n];
        d = new int[(n)];
        ptr = new int[(n)];
        q = new int[(n)];
        memset (f, 0, n*n * sizeof f[0]);
    };
 
    int graph_delete(){
        delete[] f;
        delete[] c;
        delete[] d;
        delete[] q;
        delete[] ptr;
        return 0;
    }
 
 
    bool bfs() {
        int qh=0, qt=0;
        q[qt++] = s;
        memset (d, -1, n * sizeof d[0]);
        d[s] = 0;
 
        while (qh < qt) {
            int v = q[qh++];
            for (int to=0; to<n; ++to)
                if (d[to] == -1 && f[v*n+to] < c[v*n+to]) {
                    q[qt++] = to;
                    d[to] = d[v] + 1;
                }
        }
        return d[t] != -1;
    }
 
    ll dfs (int v, int flow) {
        if (!flow)  return 0;
        if (v == t)  return flow;
        for (int & to=ptr[v]; to<n; ++to) {
            if (d[to] != d[v] + 1)  continue;
            ll pushed = dfs (to, min (flow, c[v*n+to] - f[v*n+to]));
            if (pushed) {
                f[v*n+to] += pushed;
                f[to*n+v] -= pushed;
                return pushed;
            }
        }
        return 0;
    }
 
    ll dinic() {
        ll flow = 0;
        for (;;) {
            if (!bfs())  break;
            memset (ptr, 0, n * sizeof ptr[0]);
            while (int pushed = dfs (s, INF)){
                flow += pushed;
            }
        }
        return flow;
    }
 
};
 
 
 
int main()
{
    int nn, n, m, a, b, max, wide, min_wide;
    while (scanf("%d%d", &nn, &m)){
        if ((nn == 0) && (m == 0)) break;
 
        int n = nn + 2;
        int *c = new int[n*n];
 
        memset (c, 0, n*n * sizeof c[0]);
 
        for (int i=1; i<n-1; ++i){
            scanf("%d", &a);
            if (a == 1){
                c[i] = 1;
            } else {
                c[i*n + n-1] = 1;
            }
        }
 
        for (int i=0; i<m; i++) {
            scanf("%d%d", &a, &b);
            c[a*n+b] = 1;
            c[b*n+a] = 1;
        }
 
        Graph g(n, 0, n-1, c);
        min_wide = g.dinic();
        int i = g.graph_delete();
        printf("%d\n", min_wide);
    }
    return 0;
}