hdu4067 费用流（混合欧拉的宽展和延伸）

题意：

给以一个图，每个有向边都有两个权值，a,b其中a是保留这条边的花费，b是删除这条边的花费，让你删去一些边使图满足一下要求：

（1）只有一个起点和一个终点

（2）所有的边都是又向的（题目给的就是有向的）

（3）对于起点，出度 = 入度 + 1

（4）对于终点，入度 = 出度 + 1

（5）其他的点出度 = 入度

求满足要求时的花费最小。

思路：

仔细一看要求，貌似是在求一个“欧拉路”，（但是图不一定是连通的），如果我们直接把t-s连起来就是在求所有出度=入度的最小了，也就是在求一些欧拉回路，第一反应以为是混合欧拉呢，但是对于混合欧拉是用流而不是费用流，而且混合欧拉里面也不设计到费用，但是他们有很大的相似之处，这个题目做了好久，是因为自己想不出来，同时网上的的解题报告很少，并且有的根本就写错了，还有就是网上没有说为什么，只有怎么建图，所以想了好久才明白，思路不怎么好说，我尽量去描述清楚，一边建图一遍说吧。

（1）对于每一条边，我们先选择a,b中最小的加在sum里

//先选择最小的，最为当前的选择，最后在用sum + 调整的代价就行了。

（2）如果a <= b sum += a ,连接边b -> a,流量 1 ，费用b - a

//a小我们选择a，选择a也就是我们当前打算要这条边，此时我们建立b->a是为了反悔的时候用的，b - a 是因为反悔的时候要花费的代价是 b-a,因为有一部分是放在sum里了。

因为我们选择了这条边，此时还要记录度数,我们虽然建的是b->a但度数要这样，in[b]++,

out[a] ++,因为b->a是为了反悔用的，我们的决策是在图里建了一条a->b的边，所以度数是那样存的，不要弄混了。

（3）如果b < a sum += b ,连接边a -> b,流量 1，费用a - b

// b小于a ,当前我们的选择是不连这条边，a -> b 是为了后悔的时候用的，后悔的时候我们只要在花费a - b就可以把不连变成连了，有一个关键地方就是对于这种决策不要计算入度和出度，因为我们选择的是不连边，所以当前的决策里面不设计到度数的改变。

（4）因为我们要把图处理成所有点的出度=入度，所以我们还得吧in[s] ++ ,out[t] ++,

记住只是改度数，而没有去连边，只是虚拟的去连边。

（5）最后我们要设立一个超级原点S和超级汇点T,对于所有点如果in[i] > out[i],

连接 S->i ,流量为in[i] - out[i] ,费用 0，否则连接i->T,流量out[i] - in[i],

费用0。

// 这个位置一定要理解好，不要和混合欧拉混了，混合欧拉是in[i] < out[i],连接

S->i,流量是 (out[i] - in[i]) / 2,混合欧拉是在调整（双向边的）涉及的度数，而咱们这个题目是为了调整单向边涉及的点的度数，并且含有代价在里面，至于为什么连接S-i，和i->T的时候和混合欧拉是反的，是因为我们组开始建图的时候建的都是反边，也就是建的都是反悔的时候才跑的边，所以涉及到反向。

为了理解这个题目我画了集合图来方便大家理解，画的垃圾忘谅解。

跑一边S->T的费用流就可以选择出事l1反悔还是l2反悔了，如果对于l1,l2都不选，那么和这个差不多，只不过是虚线的方向边了，S，T的连点再调换一下，如果都选我们跑边S->T的目的是为了找出我们选择的那一个，因为毕竟l1,l2我们要选一个丢弃一个，如果是在之前我们的去最小决策就正好选了一个，丢弃了一个，那么此时的连个点出度=入度，也就没必要跑费用流了。

下面是代码。

#include<stdio.h>

#include<string.h>

#include<queue>

#define N_node 110

#define N_edge 5000

#define INF 1000000000



using namespace std;

typedef struct

{

   int from ,to ,next;

   int cost ,flow;

}STAR;

STAR E[N_edge];

int list[N_node] ,tot;

int s_x[N_node];

int mer[N_edge];

int in[N_node] ,out[N_node];

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;

      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 MCMF_Spfa(int s ,int t ,int n ,int ss)

{

   int maxflow ,mincost ,minflow;

   maxflow = mincost = 0;

   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 += E[i].cost * minflow;

      }

      maxflow += minflow;

   }

   if(maxflow != ss) return -1;

   return mincost;

}

int main ()

{

   int tt ,n ,m ,s ,t ,S ,T ,i;

   int cas = 1;

   int a ,b ,c ,d;

   scanf("%d" ,&tt);

   while(tt--)

   {

      scanf("%d %d %d %d" ,&n ,&m ,&s ,&t);

      S = 0 ,T = n + 1;

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

      tot = 1;

      memset(in ,0 ,sizeof(in));

      memset(out ,0 ,sizeof(out));

      in[s] ++ ,out[t] ++;

      int sum = 0;

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

      {

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

         if(c <= d)

         {

            add(b ,a ,d - c ,1);

            sum += c;

            in[b]++ ,out[a] ++;

         }

         else

         {

            add(a ,b ,c - d ,1);

            sum += d;

         }

      }

      int ss = 0 ,sss = 0;

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

      {

         if(in[i] >= out[i])

         {

            add(S ,i ,0 ,in[i] - out[i]);

            ss += (in[i] - out[i]);

         }

         else

         {

            add(i ,T ,0 ,out[i] - in[i]);

            sss += (out[i] - in[i]);

         }

      }

      int ans = MCMF_Spfa(S ,T ,n + 1 ,ss);

      printf("Case %d: " ,cas ++);

      if(ans == -1 || ss != sss)puts("impossible");

      else printf("%d\n" ,ans + sum);

   }

   return 0;

}

巴特西

hdu4067 费用流（混合欧拉的宽展和延伸）

最新文章

热门文章