POJ 2135 简单费用流

题意：

题意是一个人他要从牧场1走到牧场n然后在走回来，每条路径只走一次，问全程的最短路径是多少。

思路：

这个题目挺简单的吧，首先要保证每条边只能走一次，然后还要要求费用最小，那么我们可以直接跑费用流啊!还有题目说的是去了又回来，这个地方我们可以直接一次跑出两条路径，就是起始的时候的流量是2就行了，然后一遍费用流，然后就wa了，这个题目最坑人的地方就是他的输入叙述，说的什么The starting field, the end field, and the path's length，这个我没猜错应该是说的有向边的意思吧，然后就是wa，改成无向边就行了。别的没啥。

#include<stdio.h>

#include<string.h>

#include<queue>

#define N_node 1000 + 10

#define N_edge 50000 + 200

#define INF 1000000000

using namespace std;

typedef struct

{

   int from ,to ,next ,cost ,flow;

}STAR;

STAR E[N_edge];

int list[N_node] ,tot;

int s_x[N_node] ,mer[N_edge];

void add(int a ,int b ,int c ,int d)

{

   E[++tot].from = a;

   E[tot].to = b;

   E[tot].cost = c;

   E[tot].flow = d;

   E[tot].next = list[a];

   list[a] = tot;

   E[++tot].from = b;

   E[tot].to = a;

   E[tot].cost = -c;

   E[tot].flow = 0;

   E[tot].next = list[b];

   list[b] = tot;

}

bool spfa(int s ,int t ,int n)

{

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

   s_x[i] = INF;

   int mark[N_node] = {0};

   s_x[s] = 0 ,mark[s] = 1;

   queue<int>q;

   q.push(s);

   memset(mer ,255 ,sizeof(mer));

   while(!q.empty())

   {

      int xin ,tou = q.front();

      q.pop();

      mark[tou] = 0;

      for(int k = list[tou] ;k; k = E[k].next)

      {

         xin = E[k].to;

         if(s_x[xin] > s_x[tou] + E[k].cost && E[k].flow)

         {

            s_x[xin] = s_x[tou] + E[k].cost;

            mer[xin] = k;

            if(!mark[xin])

            {

               mark[xin] = 1;

               q.push(xin);

            }

         }

      }

   }

   return mer[t] != -1;

}

int M_C_Flow(int s ,int t ,int n)

{

   int mincost = 0 ,maxflow = 0 ,minflow;

   while(spfa(s ,t ,n))

   {

      minflow = INF;

      for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])

      if(minflow > E[i].flow) minflow = E[i].flow;

      for(int i = mer[t] ;i + 1 ;i = mer[E[i].from])

      {

         E[i].flow -= minflow;

         E[i^1].flow += minflow;

         mincost += minflow * E[i].cost;

      }

      maxflow += minflow;

   }

   return mincost;

}

int main ()

{

   int n ,m ,i ,a ,b ,c;

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

   {

      memset(list ,0 ,sizeof(list));

      tot = 1;

      for(i = 1 ;i <= m ;i ++)

      {

         scanf("%d %d %d" ,&a ,&b ,&c);

         add(a ,b ,c ,1);

         add(b ,a ,c ,1);

      }

      add(0 ,1 ,0 ,2);

      printf("%d\n" ,M_C_Flow(0 ,n ,n));

   }

   return 0;

}

巴特西

POJ 2135 简单费用流

最新文章

热门文章