图论：费用流-SPFA+EK

利用SPFA+EK算法解决费用流问题

例题不够裸，但是还是很有说服力的，这里以Codevs1227的方格取数2为例子来介绍费用流问题

这个题难点在建图上，我感觉以后还要把网络流建模想明白才能下手去做这种题，老实说挺难的

先直接给出建图的代码：

scanf("%d",&x);

            //把每个节点拆成两个，分别为ai和bi

            //ai向bi连边，费用为权值，容量为1

            //再连边，费用为0，容量为k，保证联通

            addedge((i-)*n+j,(i-)*n+j+n*n,,x);

            addedge((i-)*n+j,(i-)*n+j+n*n,k,);

            //让bi能往下面或者左面走

            if(j<n)

                addedge((i-)*n+j+n*n,(i-)*n+j+,k,);

            if(i<n)

                addedge((i-)*n+j+n*n,i*n+j,k,);

然后给出完整实现，请记住cnt初始必须是1，为了和^配套使用

否则RE？？？

差点儿把以后的自己坑死

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 const int maxm=;

 const int INF=0x7fffffff;

 int n,k,cnt=;

 bool inq[maxn];

 int g[maxn],dis[maxn],q[maxm],from[maxn];

 long long ans;

 struct Edge{int from,to,v,c,next;}e[maxm];

 void addedge(int u,int v,int w,int c)  //cost是费用

 {

     e[++cnt].from=u;e[cnt].to=v;e[cnt].v=w;e[cnt].c=c;

     e[cnt].next=g[u];g[u]=cnt;

     e[++cnt].from=v;e[cnt].to=u;e[cnt].v=;e[cnt].c=-c;

     e[cnt].next=g[v];g[v]=cnt;

 }

 bool spfa()

 {

     int t=,w=,u;

     memset(dis,-,sizeof(dis));

     q[]=;dis[]=;inq[]=;

     while(t<w)

     {

         u=q[t];t++;

         for(int tmp=g[u];tmp;tmp=e[tmp].next)

         {

             if(e[tmp].v>&&dis[u]+e[tmp].c>dis[e[tmp].to])

             {

                 dis[e[tmp].to]=dis[u]+e[tmp].c;

                 from[e[tmp].to]=tmp;

                 if(!inq[e[tmp].to])

                     {q[w]=e[tmp].to;w++;inq[e[tmp].to]=;}

             }

         }

         inq[u]=;

     }

     if(dis[]==-) return ;

     return ;

 }

 void mincf()

 {

     int sum=INF;

     int tmp=from[];

     while(tmp)

     {

         sum=min(sum,e[tmp].v);

         tmp=from[e[tmp].from];

     }

     tmp=from[];

     while(tmp)

     {

         e[tmp].v-=sum;

         e[tmp^].v+=sum;

         ans+=sum*e[tmp].c;

         tmp=from[e[tmp].from];

     }

 }

 int main()

 {

     int x;

     scanf("%d%d",&n,&k);

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

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

         {

             scanf("%d",&x);

             //把每个节点拆成两个，分别为ai和bi

             //ai向bi连边，费用为权值，容量为1

             //再连边，费用为0，容量为k，保证联通

             addedge((i-)*n+j,(i-)*n+j+n*n,,x);

             addedge((i-)*n+j,(i-)*n+j+n*n,k,);

             //让bi能往下面或者左面走

             if(j<n)

                 addedge((i-)*n+j+n*n,(i-)*n+j+,k,);

             if(i<n)

                 addedge((i-)*n+j+n*n,i*n+j,k,);

         }

     //源点和汇点

     addedge(,,k,);

     addedge(n*n*,,k,);

     while(spfa()) mincf();

     printf("%lld",ans);

     return ;

 }

还有一点就是这个题是最大费用最大流，最小费用最大流还有ZKW费用流以后再介绍