欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UOJ #3265. 志愿者招募加强版

程序员文章站 2022-07-13 11:02:49
...

题意:UOJ #3265. 志愿者招募加强版

思路:线性规划的题都可以用网络流来解决。

        具体思路是  差分之后每一对正的和负的之间连边。inf的边起调节作用。

#include <bits/stdc++.h>
using namespace std;
typedef int lint;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int maxk = 1000005;
struct EDGE {
    int from, to, next, cost, cap;  //  如果需要修改 cost为LL
};
namespace MFMC {
    const static int maxn = 1011;
    const static int maxm = 500005;
    EDGE edge[maxm];
    int tot, he[maxn], n;
    void init(int _n) {
        tot = 0;
        n = _n + 1;
        memset(he, -1, n * sizeof(int));
    }
    void Add(int u, int v, int cap,int cost) {   //  如果需要修改 cost为LL
        edge[tot] = EDGE{u, v, he[u], cost, cap};
        he[u] = tot++;
    }
    void add(int u, int v, int cap,int cost) {  //  如果需要修改 cost为LL
        Add(u, v,  cap,cost);
        Add(v, u,  0,-cost);
    }
//O(VE)
//record_e[i]是fa[i]->i的边的编号
    template<typename DT>
    void spfa(int s, DT dist[], int rec[]) {
        queue<int> q;
        static bool inq[maxn];

        memset(dist, 0x3f, n * sizeof(DT));
        memset(inq, 0, n * sizeof(bool));
        memset(rec, -1, n * sizeof(int));
        q.push(s);
        dist[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (int e = he[u]; ~e; e = edge[e].next) {
                if (0 == edge[e].cap)
                    continue;
                int v = edge[e].to;
                if (dist[v] > dist[u] + edge[e].cost) {
                    dist[v] = dist[u] + edge[e].cost;
                    rec[v] = e;
                    if (!inq[v]) {
                        q.push(v);
                        inq[v] = 1;
                    }
                }
            }
        }
    }

    template<typename DT>
    void dijkstra(int s, DT dist[], int rec[]) {
        priority_queue<pair<DT, int> > q;//-dist, vertex

        memset(dist, 0x3f, n * sizeof(DT));
        memset(rec, -1, n * sizeof(int));
        dist[s] = 0;
        q.push(make_pair(0, s));
        while (!q.empty()) {
            s = q.top().second;
            DT c = -q.top().first;
            q.pop();
            if (c != dist[s]) continue;
            for (int e = he[s]; ~e; e = edge[e].next) {
                if (0 == edge[e].cap) continue;
                int v = edge[e].to;
                if (dist[v] > c + edge[e].cost) {
                    dist[v] = c + edge[e].cost;
                    rec[v] = e;
                    q.push(make_pair(-dist[v], v));
                }
            }
        }
    }

//Need dijkstra_GRAPH_EDGES_PQ
//O(FE log(E)),F is the maximum flow

    template<typename FT, typename CT>
    void mfmc(int s, int t, FT &maxflow, CT &mincost) {
        CT inf;
        memset(&inf, 0x3f, sizeof(CT));
        static CT dist[maxn];
        static int rec_e[maxn];
        maxflow = mincost = 0;
        CT realdist = 0;    //real distance from s to t

        bool first = true;
        while (1) {
            if (first) {
                spfa( s, dist, rec_e);
                first = false;
            } else {
                //dijkstra( s, dist, rec_e);
                spfa( s, dist, rec_e);
            }
            if (inf == dist[t])
                break;
            FT minF = numeric_limits<FT>::max();
            for (int e = rec_e[t]; ~e; e = rec_e[edge[e].from])
                minF = min(minF, (FT) edge[e].cap);
            maxflow += minF;
            realdist += dist[t];
            mincost += minF * realdist;
            for (int e = rec_e[t]; ~e; e = rec_e[edge[e].from]) {
                edge[e].cap -= minF;
                edge[e ^ 1].cap += minF;
            }
            for (int e = 0; e < tot; ++e) {
                EDGE &ed = edge[e];
                ed.cost += dist[ed.from] - dist[ed.to];
            }
        }
    }
};
int l[maxk],r[maxk];
int main(){
    int n,m,a;
    scanf("%d%d",&n,&m);
    int S = 0,T = n+2;
    MFMC::init(T);
    for( int i = 1;i <= n;i++ ){
        scanf("%d",&a);
        MFMC::add( i,T,a,0 );
        MFMC::add( S,i+1,a,0 );
        MFMC::add( i,i+1,inf,0 );
    }
    for( int i = 1;i <= m;i++ ){
        int k;scanf("%d",&k);
        for( int j = 1;j <= k;j++ ){
            scanf("%d%d",&l[j],&r[j]);
        }
        int c;
        scanf("%d",&c);
        for( int j = 1;j <= k;j++ ){
            MFMC::add( r[j]+1,l[j],inf,c );
        }
    }
    int mincost,maxflow;
    MFMC::mfmc(S,T,maxflow,mincost);
    //cout << maxflow << endl;
    printf("%d\n",mincost);
    /*int x,num;
    int n,m;
    scanf("%d%d",&n,&m);
    int S=0,T=n+2;
    MFMC::init(T);*/
    /*MFMC::add(S,1,inf,0);
    for(int i=1;i<=n;++i) {
        int x;scanf("%d",&x);
        MFMC::add(i,i+1,inf-x,0);
    }*/
    /*for( int i = 1;i <= n;i++ ){
        int a;
        scanf("%d",&a);
        MFMC::add( i,T,a,0 );
        MFMC::add( S,i+1,a,0 );
        MFMC::add( i,i+1,inf,0 );
    }
    for(int i=1;i<=m;++i) {
        scanf("%d",&num);
        for(int j=1;j<=num;++j) {
            scanf("%d%d",&l[j],&r[j]);
        }
        scanf("%d",&x);
        for(int j=1;j<=num;++j) MFMC::add(r[j]+1,l[j],inf,x);
    }
    int maxflow = 0,mincost = 0;
    MFMC::mfmc( S,T,maxflow,mincost );
    cout << maxflow << endl;
    printf("%d\n",mincost);*/
    return 0;
}