最小费用最大流：无向图（所以必须用邻接表）+当流量为D时的最小费用（即限制流量在D，求最大流）

题意：就是给你一个无向图，给出所有的无向边和它们的单位费用（题中说了不会有平行边），然后给出D,K，K是指每条无向边的容量固定为K，然后问当流量为D时最小费用是多少，如果流量无法得到D这个数值，那么就输出Impossible.  解决这个问题的方法就是限制流量，加一个新的源点（或者汇点，道理一样），增加一条有向边，就是新的源点指向原本的源点，这条有向边的容量就是D，费用是0，然后求新源点到汇点的最小费用最大流，可以知道，求出来的最大流一定是小于等于D的（同样是最大水流取决于最细水管的道理，水流必须从新的源点出发，必须而且只能经过新源点指向原本源点的那条有向边，所以最大流量只能小于等于这条有向边的容量D）

然后就是邻接表建图的问题

对于最大流问题，没有存在的有向边我们用cap[u][v]=0表示容量为0，而最小费用问题中即便不存在的边我们也要用cost[v][u]=-cost[u][v]表示取反的费用，所以最小费中一个有向边要变为两条来处理，所以一个无向边要变成两个有向边，再变两条，也就是一条无向边变为四条有向边处理

 

然后就是白书中介绍的求最小费用最大流问题的模板   SPFA+增广   不过要注意邻接表和邻接矩阵记录路径的方法不同，而且增广时也有区别，具体看代码

 

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;const long long INF=1000000000000000000;#define N 110#define M 5010struct edge{    int u,v,next;    long long cost,flow;}e[M*4];int n,m,s,t;long long D,K,F,C;long long d[N];int edgenum;   //最终边集数组里面的边的条数int first[N],p[N];void add(int u , int v ,long long c , long long f){    e[edgenum].u=u;    e[edgenum].v=v;    e[edgenum].cost=c;    e[edgenum].flow=f;    e[edgenum].next=first[u];    first[u]=edgenum;    edgenum++;  //边集数组当前的下标}void print_graph(){    for(int i=0; i<=n; i++)    {        printf("%d:_______________\n",i);        for(int k=first[i]; k!=-1; k=e[k].next)            printf("%d\\%lld\\%lld\n",e[k].v,e[k].cost,e[k].flow);    }    printf("**********\n");    return ;}void SPFA(){    queue 
        
          q;    int vis[N];    for(int i=0; i<=n; i++)     d[i]=INF;     memset(vis,0,sizeof(vis));    memset(p,-1,sizeof(p));     d[s]=0; vis[s]=1;    q.push(s);    while(!q.empty())    {        int u=q.front(); vis[u]=0; q.pop();        for(int k=first[u]; k!=-1; k=e[k].next) //遍历点u的邻接表        {            int v=e[k].v;            long long c=e[k].cost , f=e[k].flow;            if( f && d[u]+c < d[v])            {                p[v]=k;                 //邻接表的记录方法是记录点v但是所对应的边k，就可以知道该边的所有信息了                d[v]=d[u]+c;                if(!vis[v])                {                    vis[v]=1;                    q.push(v);                }            }        }    }    return ;}int mincost_maxflow(){    F=C=0;    while(1)    {        SPFA();        if(d[t]==INF)  break;                long long a=INF;        for(int k=p[t]; k!=-1; k=p[e[k].u]) //这里的k是指第k条边，不再是邻接矩阵里面的顶点            if(e[k].flow
         
          ,费用c，容量K            add(vv[i] , uu[i] , -cc[i] , 0);  //其反向，费用取反，容量为0            add(vv[i] , uu[i] , cc[i] , K);  //有向边
          
           ,费用c，容量K add(uu[i] , vv[i] , -cc[i] , 0); //其反向，费用取反，容量为0 } add(0,1,0,D); add(1,0,0,0); //最后要加上一个有向边<0,1>，和它的反向，即先添加的一个源点 //容量限制为D，费用为0 //print_graph(); //测试函数 s=0; t=n; mincost_maxflow(); if(F==D) //最小费用最大流 printf("%lld\n",C); else printf("Impossible.\n"); } return 0;}