hdu4494

题意:

给你一些任务,每个任务有自己的开始时间和需要多久能干完,还有就是每个任务都需要一些人,这些人有最多五个种类,各种类之间的人不能相互替换,但是某些工人干完这个活后如果可以在另一个任务还没开始的时候赶过去,也可以帮那个任务干活,干的是自己的属性的活,还有一个关键的点就是所有的任务必须人齐了才能干,最后问你最少要多少个人能把活干完..

思路:

费用流,就是在满流(任务都必须干完)的前提下花费最少,一开始想的是吧每个点先拆成五个点,代表不同属性的人,sb了,写来写去自己都蒙了,其实每个属性的人之间没有关系的话我们可以单独算啊,就是跑5变费用流被,最后把他们加起来就好了,这样就很容易写了,下面说重点,怎么建图.

首先要有一个超级源点和汇点,不解释..

然后就是对于每一个点,我们要拆成两个点(这两个点之间没有边),这两个点不是平时我们那种限流的点,一个是自己,另一个是用来连接自己可以给别的任务送人用的..对于每一个自己的点,我们连一条边,流量inf,费用1,很容易理解,总部有无数的人,但是你要是用一个就得付出一个代价..

然后就是对于每一个拆出来的点,原点像它连接一条边,流量是need,费用是0,因为当前的这个点最多能给别人提供need的人,而且是免费的...

最后就是找任务个任务之间的关系了,如果 work[i].p + work[i].d + dis(i ,j) <= work[j].p ,就还来的及,那么就用i拆出来的那个点,去连接j的那个点...

大概就是这个样子,自己表达能力不好,如果没看懂画一下子就明白了...

#include<stdio.h>

#include<string.h>

#include<queue>

#include<math.h>

#define N_node 350

#define N_edge 30000

#define inf 1000000000



using namespace std;

typedef struct

{

   int from ,to ,cost ,flow ,next;

}STAR;

typedef struct

{

   double x ,y;

   int p ,d;

   int need[6];

}WORK;

STAR E[N_edge];

WORK work[N_node];

int list[N_node] ,tot;

int 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;

}

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

{

   int s_x[N_node];

   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 tou ,xin;

      tou = q.front();

      q.pop();

      mark[tou] = 0;

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

      {

         xin = E[k].to;

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

         {

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

   int maxflow = 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;

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

       }

       maxflow += minflow;

   }

   return ans;

}

int main ()

{

   int t ,n ,m ,i ,j;

   double sx ,sy;

   int a ,b, c ,d;

   scanf("%d" ,&t);

   while(t--)

   {

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

      scanf("%lf %lf" ,&sx ,&sy);

      n --;

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

      {

         scanf("%lf %lf %d %d" ,&work[i].x ,&work[i].y ,&work[i].p ,&work[i].d);

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

         scanf("%d" ,&work[i].need[j]);

      }

      int ans = 0;

      for(int ii = 1 ;ii <= m ;ii ++)

      {

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

         tot = 1;

         int s = 0 ,t = n * 2 + 1;

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

         {

            add(s ,i ,1 ,inf) ,add(i ,s ,-1 ,0);

            add(i ,t ,0 ,work[i].need[ii]) ,add(t ,i ,-0 ,0);

            add(s ,i + n ,0 ,work[i].need[ii]) ,add(i + n ,s ,-0 ,0);

         }

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

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

         {

            if(i == j) continue;

            double dis = pow(work[i].x - work[j].x ,2.0) + pow(work[i].y - work[j].y ,2.0);

            dis = sqrt(dis);

            if(work[i].p + work[i].d + dis <= work[j].p)

            add(i + n ,j ,0 ,inf) ,add(j ,i + n ,-0 ,0);

         }

         ans += M_C_flow(0 ,t ,t);

       }

       printf("%d\n" ,ans);

   }

   return 0;

}

巴特西

hdu4494

最新文章

热门文章