首页 > 代码库 > HDU 4862 JUMP 最小费用最大流

HDU 4862 JUMP 最小费用最大流

2024-07-13 17:39:04   226人阅读

2014 多校的B题，由于我不怎么搞图论，当时碰到这个题目，我怎么想都没往网络流方面弄，不过网络流真的是个好东西，对于状态多变，无法用动规或者数据结构来很好表示的时候，非常有用

这个题目要求每个点一定要访问到，并且每次访问的是没访问过的点，跳跃的方向为向右或者向下。

建图的时候，分成二分图，从一个超级源点向x部分建cap为1 cost为0的点，对所以可到达的点从x到y建cap为1，cost根据题目算出来，不过要算负值，因为我们要求得实际是最大费用，最后对结果求相反数即可。所有y部分的点对超级汇点T建cap为1，cost为0的点。

但是这样还是没满足只能走k次的条件，所以得额外建一个点，从S到该点建cap为k，cost为0的点，再用这个点对y部分所有点建cap为1，cost为0的点，因为每次从x部流到y部最终流到T的点，都是不包括起始点的，用这个额外点向y部分供应最多k次（不一定要k个）的起始点量即可

最后求得一定要流量为 N*M才算走通，此外，cost的相反数即为所求最大费用

用的是大白书上的最小费用最大模板，复杂度应该是n*m*某个系数

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;const int maxn = 310;struct Edge{    int from,to,cap,flow,cost;};struct MCMF{  int n,m,s,t;  vector<Edge> edges;  vector<int> G[maxn];  int inq[maxn];  int d[maxn];  int p[maxn];  int a[maxn];  void init(int n){      this->n=n;      for (int i=0;i<=n;i++) G[i].clear();      edges.clear();  }  void add(int from,int to,int cap,int cost)  {      edges.push_back((Edge){from,to,cap,0,cost});      edges.push_back((Edge){to,from,0,0,-cost});      m=edges.size();      G[from].push_back(m-2);      G[to].push_back(m-1);  }} TF;char mat[15][15];int N,M,K;int id[15][15];int S,T;bool Bellman(int s,int t,int &flow,int &cost){    for (int i=0;i<=2*N*M+2;i++) TF.d[i]=(1<<30);    memset(TF.inq,0,sizeof TF.inq);    TF.d[s]=0;TF.inq[s]=1;TF.a[s]=1<<30;    queue<int> Q;    Q.push(s);    while (!Q.empty())    {        int u=Q.front();Q.pop();        TF.inq[u]=0;        for (int i=0;i<TF.G[u].size();i++){            Edge & e=TF.edges[TF.G[u][i]];            if (e.cap>e.flow && TF.d[e.to]>TF.d[u]+e.cost){                TF.d[e.to]=TF.d[u]+e.cost;                TF.p[e.to]=TF.G[u][i];                TF.a[e.to]=min(TF.a[u],e.cap-e.flow);                if (!TF.inq[e.to]) {Q.push(e.to);TF.inq[e.to]=1;}            }        }    }    if (TF.d[t]>=(1<<30)) return false;    flow+=TF.a[t];    cost+=TF.d[t];    int u=t;    while (u!=s){        TF.edges[TF.p[u]].flow+=TF.a[t];        TF.edges[TF.p[u]^1].flow-=TF.a[t];        u=TF.edges[TF.p[u]].from;    }    return true;}int mincost(){    int flow=0,cost=0;    while (Bellman(S,T,flow,cost));    if (flow==N*M)    return -cost;    else return -1;}int main(){    int t;    scanf("%d",&t);    int kase=0;    while (t--)    {        scanf("%d%d%d",&N,&M,&K);        S=0,T=2*N*M+2;        TF.init(T);        for (int i=1;i<=N;i++) scanf("%s",mat[i]+1);        for (int i=1;i<=N;i++){          for (int c=1;c<=M;c++){            for (int j=i+1;j<=N;j++){                int cost=0;                cost+=j-i-1;                if (mat[i][c]==mat[j][c]) cost-=mat[i][c]-‘0‘;                TF.add((i-1)*M+c,N*M+(j-1)*M+c,1,cost);            }            for (int j=c+1;j<=M;j++){               int cost=0;               cost+=j-c-1;               if (mat[i][c]==mat[i][j]) cost-=mat[i][c]-‘0‘;               TF.add((i-1)*M+c,N*M+(i-1)*M+j,1,cost);            }          }        }        for (int i=1;i<=N;i++){            for (int j=1;j<=M;j++){                TF.add(S,(i-1)*M+j,1,0);                TF.add(N*M+(i-1)*M+j,T,1,0);            }        }        TF.add(S,2*N*M+1,K,0);        for (int i=N*M+1;i<=2*N*M;i++){            TF.add(2*N*M+1,i,1,0);        }        printf("Case %d : %d\n",++kase,mincost());    }    return 0;}

　　


联系
我们