hdu4411 经典费用里建图

题意:

给以一个无向图,0 - n,警察在0,他们有k个警队,要派一些警队去1--n个城市抓小偷,

问所有吧所有小偷全抓到然后在返回0的最小路径和是多少,当地i个城市被攻击的时候他会通知i-1城市,也就是说要么同时消灭他俩,要么消灭i-1在消灭i;

思路:

经典的费用流建图 ,先来一遍floyd处理下图 ,首先虚拟出来源点s ,终点t ,超级源点ss,

建图:

from to cost flow

ss s 0 k //限制最多k个警队

s i map[0][i] 1 // 出发去

i i + n -INF 1 //-INF 是为了保证每一个都得跑

i + n t map[0][i] 1 // 回家

i + n j map[i][j] 1 //i < j ,收拾完i再去城镇j收拾j

s t 0 1 //用这个边处理没有出动的警队

#include<stdio.h>

#include<string.h>

#include<queue>

#define N_node 210

#define N_edge 20000

#define INF 10000000



using namespace std;

typedef struct

{

   int from ,to ,cost ,flow ,next;

}STAR;

STAR E[N_edge];

int list[N_node] ,tot;

int mer[N_edge];

int s_x[N_node];

int map[N_node][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)

{

   int mark[N_node] = {0};

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

   s_x[i] = INF;

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

   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 maxflow = 0,minflow;

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

      }

      maxflow += minflow;

   }

   return mincost;

}

int minn(int x ,int y)

{

   return x < y ? x : y;

}

void floyd(int n)

{

   int i ,j ,k;

   for(k = 0 ;k <= n ;k ++)

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

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

   map[i][j] = minn(map[i][j] ,map[i][k] + map[k][j]);

} 

int main ()

{

   int n ,m, i ,j ,K;

   int a ,b ,c;

   int ss ,s ,t;

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

   {

      ss = 0 ,s = n + n + 1 ,t = n + n + 1 + 1;

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

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

      {

         if(i == j) map[i][j] = 0;

         else map[i][j] = INF;

      }

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

      {

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

         map[a][b] = map[b][a] = minn(map[a][b] ,c);

      }

      floyd(n);

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

      tot = 1;

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

      {

         add(s ,i ,map[0][i] ,1);

         add(i ,i + n ,-INF ,1);

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

         add(i + n ,j ,map[i][j] ,1);

         add(i + n ,t ,map[i][0] ,1);

      }

      add(ss ,s ,0 ,K);

      add(s ,t ,0 ,K);

      int cost = MCMF_SPFA(ss ,t ,n + n + 1 + 1);

      printf("%d\n" ,cost + n * INF);

   }

   return 0;

}

巴特西

hdu4411 经典费用里建图

最新文章

热门文章