hdu 4322 最大费用流

时间：2021-03-30 21:11:27

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4322

#include <cstdio>

#include <cstring>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

using namespace std;

const int maxe = ;

const int maxn = ;

const int INF  = 0x3f3f3f;

struct Edge{

    int u,v,flow,cap,cost;

    int next;

    Edge(int u=,int v=,int flow=,int cap=,int cost=,int next=):

        u(u), v(v),  flow(flow), cap(cap),  cost(cost), next(next) {}

};

struct MCMF{

    int d[maxn];

    bool inq[maxn];

    Edge edges[maxe];

    int head[maxn],cnt;

    int pa[maxn];   //用于回溯找增广路。

    int res[maxn];

    void init(){

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

        cnt = ;

    }

    void addedge(int u,int v,int cap,int cost){

        edges[cnt] = Edge(u,v,,cap,cost,head[u]);

        head[u] = cnt++;

        edges[cnt] = Edge(v,u,,,-cost,head[v]);

        head[v] = cnt++;

    }

    bool SPFA(int s,int t,int& flow,int& cost){

        memset(inq,,sizeof(inq));

        memset(d,-0x3f,sizeof(d));     //这个才是WA无数次的原因，看别人的代码才知道。

        queue<int> Q;

        Q.push(s);

        d[s] = ;        inq[s] = true;

        res[s] = INF;    res[t] = ;

        while(!Q.empty()){

            int u = Q.front();  Q.pop();

            inq[u] = false;

            for(int i=head[u];i!=-;i=edges[i].next){

                Edge& e = edges[i];

                if(e.cap > e.flow && d[e.v] < d[u] + e.cost){

                     d[e.v] = d[u] + e.cost;

                     pa[e.v] = i;

                     res[e.v] = min(res[u],e.cap-e.flow);

                     if(!inq[e.v]){

                        Q.push(e.v);   inq[e.v] = true;

                     }

                }

            }

        }

        if(res[t] == )  return false;

        flow += res[t];

        cost += res[t]*d[t];

        for(int i=t;i!=s;i=edges[pa[i]].u){

            edges[pa[i]].flow   += res[t];

            edges[pa[i]^].flow -= res[t];

        }

        return true;

    }

    bool MaxCost(int s,int t,int N,int sumB){

        int flow = ,cost = ;

        while(SPFA(s,t,flow,cost)) {}

        return N - flow >= sumB - cost;

    }

}solver;

int main()

{

    //freopen("E:\\acm\\input.txt","r",stdin);

    int T;

    cin>>T;

    for(int cas=;cas<=T;cas++){

        solver.init();

        int N,M,K;

        cin>>N>>M>>K;

        int B[maxn];

        int sumB = ;

        for(int i=;i<=M;i++)  { cin>>B[i];  sumB += B[i]; }

        int s = , t = N+M+;

        for(int i=;i<=N;i++)  solver.addedge(s,i,,);

        int like[maxn][maxn];

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

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

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

                if(like[i][j])

                    solver.addedge(j,i+N,,);

            }

 /**

        for(int i=1;i<=M;i++)

            for(int j=1;j<=N;j++){

                int flag;

                scanf("%d",&flag);

                if(flag)  solver.addedge(j,i+N,1,0);

            }

   这个代码与上面的那段功能相同，但我不知道为啥会错。我怀疑是oj的问题。

**/

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

            solver.addedge(N+i,t,B[i]/K,K);

            if(B[i]%K > )

                solver.addedge(N+i,t,,B[i]%K);

        }

        if(solver.MaxCost(s,t,N,sumB))  printf("Case #%d: YES\n",cas);

        else                            printf("Case #%d: NO\n",cas);

    }

}

相关文章