POJ 2516Minimum Cost(最小费用流+特判)

【题意】：

有N个人，M个仓库，每个人需要物品，个数都等于共同的K，仓库中有对应的K件物品的数量，随后给K个N*M矩阵（小写k, n, m表示K,N,M对应的子集），表明m个仓库到第n个人的位置运送k物品的花费，求

满足所有人的订单要求所需要的花费，如果不能满足所有人则输出-1

【思路】：

我的思路是建立源点sp，汇点tp, 把仓库和人所在的点都进行拆分，对每个仓库拆分成K个点，可以想象成一个大仓库由K个小仓库组成，每个小仓库只发放第k种物品，每个人也分成K个点，每个点接受一种k物品，sp与仓库的拆点进行连边，权重为这个小仓库存放的k物品的数量，花费为0，人的拆点与tp连边，权重为人拆点所需要的k物品的数量，费用为0，最后将仓库的拆点与人的拆点进行连边，权重为inf，费用为矩阵中对应的费用。

【重要】——>解决TLE问题

我的想法可能与网上的题解不同，我看有很多是分别跑k次费用流，最后的费用总和为结果，我在一开始也是疯狂TLE，然后加上特判就过了？

【特判】——>解决TLE

将输入分成三部分与N有关——与M有关——K个N*M矩阵

判定是否有供不应求的情况，将前两部分输入(N*K和N*K)分别存储下来，N*K代表所需要的部分，M*K代表供应的部分，对每个k进行遍历，然后求每个n的和sum1，每个m的和sum2，如果sum1>sum2则不对第三部分输入处理(K个N*M矩阵)，待输入结束后不进行费用流算法，直接输出-1即可

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

#include <algorithm>

using namespace std;

const int maxn = 1e4 + ;

const int maxe = 1e6 + ;

const int N =  + ;

const int inf = 0x3f3f3f3f;

struct edge{

    int to, w, c, next;

} ed[maxe];

int head[maxn], tot, ns;

int n, m, k, ware[N][N], p[N][N];

int sp, tp, d[maxn], pre[maxn], a[maxn];

bool inq[maxn];

inline void init(){

    memset( head, -, sizeof(head) ) ;

    tot = ;

    ns = (n+m)*k+;

    sp = ; tp = ns-;

}

inline void add( int u, int v, int w, int c ){

    ed[++tot].to = v; ed[tot].w = w; ed[tot].c = c; ed[tot].next = head[u]; head[u] = tot;

    ed[++tot].to = u; ed[tot].w = ; ed[tot].c = -c; ed[tot].next = head[v]; head[v] = tot;

}

inline bool spfa( int &flow, int &cost ){

    for( int i=; i<ns; i++ ){

        inq[i] = ;

        d[i] = inf;

    }

    queue<int> q;

    d[sp] = pre[sp] = ;

    a[sp] = inf;

    inq[sp] = ;

    q.push(sp);

    while( q.size() ){

        int x = q.front();

        q.pop();

        inq[x] = ;

        for( int i=head[x]; ~i; i=ed[i].next ){

            int y = ed[i].to;

            if( ed[i].w> && d[y]>d[x]+ed[i].c ){

                d[y] = d[x]+ed[i].c;

                pre[y] = i;

                a[y] = min(a[x], ed[i].w);

                if( !inq[y] ){

                    inq[y] = ;

                    q.push(y);

                }

            }

        }

    }

    if( d[tp]==inf ) return ;

    flow += a[tp];

    cost += a[tp]*d[tp];

    for( int x=tp; x!=sp; x=ed[pre[x]^].to ){

        ed[pre[x]].w -= a[tp];

        ed[pre[x]^].w += a[tp];

    }

    return ;

}

inline void mcmf( int &flow, int &cost ){ while(spfa(flow, cost)); }

int main(){

    while( ~scanf("%d%d%d", &n, &m, &k), (n||m||k) ){

        init();

        int num, sum = ;

        for( int i=; i<=n; i++ )

            for( int j=; j<=k; j++ ){

                scanf("%d", &p[i][j]);

                sum += p[i][j];

                add( (i-)*k+j, tp, p[i][j],  );

            }

        for( int i=; i<=m; i++ )

            for( int j=; j<=k; j++ ){

                scanf("%d", &ware[i][j]);

                add( sp, (i-)*k+j+n*k, ware[i][j],  );

            }

        bool flag = ;

        for( int i=; i<=k; i++ ){

            int sum1 = , sum2 = ;

            for( int j=; j<=n; j++ ) sum1 += p[j][i];

            for( int j=; j<=m; j++ ) sum2 += ware[j][i];

            if( sum2<sum1 ) {flag = ; break;}              //判断是否存在供不应求，如果存在则直接输出-1

        }

        for( int l=; l<=k; l++ )

            for( int i=; i<=n; i++ )

                for( int j=; j<=m; j++ ){

                    int num;

                    scanf("%d", &num);

                    if( flag ) continue;                    //如果出现供不应求则不进行处理，只读取数据即可

                    add( (j-)*k+l+n*k, (i-)*k+l, inf, num );

                }

        if( flag ){ puts("-1"); continue; }             //输出-1

        int flow = , cost = ;

        mcmf(flow, cost);

        if( flow>=sum ) printf("%d\n", cost);

        else puts("-1");

    }

    return ;

}

巴特西

POJ 2516Minimum Cost(最小费用流+特判)

最新文章

热门文章