poj 3422(最小费用最大流)

题目链接：http://poj.org/problem?id=3422

思路：求从起点到终点走k次获得的最大值，最小费用最大流的应用：将点权转化为边权，需要拆点，边容量为1，费用为该点的点权，表示该点的权值只能获取一次，另外，应该连一条容量为inf,费用为0的边，因为每条边都可以走多次。另外就是增加源点和汇点了，源点与起点连容量为k,费用为0的边，表示可以走k次，同理终点与汇点也如此。然后就是求最大费用了，这与求最小费用类似，只需将spfa函数稍作修改即可。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define MAXN 8888

 #define MAXM 4444444

 #define inf 1<<30

 struct Edge {

     int v,cap,cost,next;

 } edge[MAXM];

 int n,m,vs,vt,NE;

 int head[MAXN];

 void Insert(int u,int v,int cap,int cost)

 {

     edge[NE].v=v;

     edge[NE].cap=cap;

     edge[NE].cost=cost;

     edge[NE].next=head[u];

     head[u]=NE++;

     edge[NE].v=u;

     edge[NE].cap=;

     edge[NE].cost=-cost;

     edge[NE].next=head[v];

     head[v]=NE++;

 }

 int cur[MAXN],pre[MAXN];

 bool mark[MAXN];

 int dist[MAXN];

 bool spfa(int vs,int vt)

 {

     memset(mark,false,sizeof(mark));

     fill(dist,dist+vt+,-inf);

     dist[vs]=;

     queue<int>que;

     que.push(vs);

     while(!que.empty()) {

         int u=que.front();

         que.pop();

         mark[u]=false;

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

             int v=edge[i].v,cost=edge[i].cost;

             if(edge[i].cap>&&dist[u]+cost>dist[v]) {

                 dist[v]=dist[u]+cost;

                 pre[v]=u;

                 cur[v]=i;

                 if(!mark[v]) {

                     mark[v]=true;

                     que.push(v);

                 }

             }

         }

     }

     return dist[vt]!=-inf;

 }

 int MinCostFlow(int vs,int vt)

 {

     int flow=,cost=;

     while(spfa(vs,vt)) {

         int aug=inf;

         for(int u=vt; u!=vs; u=pre[u]) {

             aug=min(aug,edge[cur[u]].cap);

         }

         flow+=aug;

         cost+=dist[vt]*aug;

         for(int u=vt; u!=vs; u=pre[u]) {

             edge[cur[u]].cap-=aug;

             edge[cur[u]^].cap+=aug;

         }

     }

     return cost;

 }

 int map[][];

 int dir[][]= {{,},{,}};

 int main()

 {

   //  freopen("1.txt","r",stdin);

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

         NE=;

         vs=,vt=*n*n+;

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

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

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

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

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

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

                 Insert((i-)*n+j,(i-)*n+j+n*n,,map[i][j]);

                 Insert((i-)*n+j,(i-)*n+j+n*n,inf,);

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

                     int x=i+dir[k][],y=j+dir[k][];

                     if(x<=n&&y<=n)

                         Insert((i-)*n+j+n*n,(x-)*n+y,inf,);

                 }

             }

         }

         Insert(vs,,m,);

         Insert(*n*n,vt,m,);

         printf("%d\n",MinCostFlow(vs,vt));

     }

     return ;

 }

巴特西

poj 3422(最小费用最大流)

最新文章

热门文章