hdu 4309 最大流 + DFS

题意：

给以三种有向边

（1）隧道，可以过无数人，也可以藏c个人。

（2）路，只能过人（流量INF）。

（3）古桥，如果不修理可以过1个人，修理可以过无数个人，但是要花费c那么多钱同时还给了每个城市的人数，要求是城市的人去隧道里躲避，问你在躲避人数最多的前提下费用最小，费用就是修理古桥所用的钱。

思路：

先看古桥数量，最多12个，2^12 也就四千多，直接二分枚举哪些古桥是修理的，然后对于每一种状态，我们都重新建图，用最大流去找最多藏多少人，然后更新最优就行了。下面说下建图吧，这个题目的建图不难，直接建就行。

(0)建立超级远点和汇点，s,t。

(1)隧道，既然可以藏人，就可以虚拟出一个点来，比如给的隧道a(点),b(点),c(人数)

我们可以虚拟出来一个点d，add(a ,d ,INF),add(d ,b ,INF) ,add(d ,t ,c);

(2)路,这个没话说 add(a ,b ,INF);

(3)古桥，对于深搜的当前状态的当前这个古桥，如果是修理add(a ,b ,INF),如果不是修理add(a ,b ,1)这样一边重建，一边深搜更新最大值就行了。

#include<stdio.h>

#include<queue>

#include<string.h>

#define N_node 500

#define N_edge 10000

#define INF 1000000000



using namespace std;

typedef struct

{

   int to ,next ,cost;

}STAR;

typedef struct

{

   int a ,b ,c;

}NODE;

typedef struct

{

   int x ,t;

}DEP;

STAR E[N_edge];

NODE L[1100] ,G[15] ,S[25];

int n1 ,n2 ,n3;

DEP xin ,tou;

int list[N_node] ,tot;

int list1[N_node];

int deep[N_node];

int mk[15];

int pp[1100];

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

{

   E[++tot].to = b;

   E[tot].cost = c;

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

   list[a] = tot;

   E[++tot].to = a;

   E[tot].cost = 0;

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

   list[b] = tot;

}

int minn(int x ,int y)

{

   return x < y ? x : y;

}

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

{

   memset(deep ,255 ,sizeof(deep));

   deep[s] = 0;

   xin.x = s ,xin.t = 0;

   queue<DEP>q;

   q.push(xin);

   while(!q.empty())

   {

      tou = q.front();

      q.pop();

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

      {

         xin.x = E[k].to;

         xin.t = tou.t + 1;

         if(deep[xin.x] != -1 || !E[k].cost)

         continue;

         deep[xin.x] = xin.t;

         q.push(xin);

      }

   }

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

   list1[i] = list[i];

   return deep[t] != -1;

}

int DFS_flow(int s ,int t ,int flow)

{

   if(s == t) return flow;

   int nowflow = 0;

   for(int k = list1[s] ;k ;k = E[k].next)

   {

      list1[s] = k;

      int to = E[k].to;

      int c = E[k].cost;

      if(deep[to] != deep[s] + 1 || !c)

      continue;

      int tmp = DFS_flow(to ,t ,minn(c ,flow - nowflow));

      nowflow += tmp;

      E[k].cost -= tmp;

      E[k^1].cost += tmp;

      if(flow == nowflow) break;

   }

   if(!nowflow) deep[s] = 0;

   return nowflow;

}

int DINIC(int s ,int t ,int n)

{

   int ans = 0;

   while(BFS_Deep(s ,t ,n))

   {

      ans += DFS_flow(s ,t ,INF);

   }

   return ans;

}

void Rebuid(int n)

{

   memset(list ,0 ,sizeof(list)) ,tot = 1;

   int T = n + n1 + 1;

   for(int i = 1 ;i <= n1 ;i ++)

   {

      int a = S[i].a ,b = S[i].b ,c = S[i].c;

      add(i + n ,T ,c);

      add(a ,i + n ,INF) ,add(i + n ,b ,INF);

   }

   for(int i = 1 ;i <= n2 ;i ++)

   add(L[i].a ,L[i].b ,INF);

   for(int i = 1 ;i <= n3 ;i ++)

   if(mk[i]) add(G[i].a ,G[i].b ,INF);

   else add(G[i].a ,G[i].b ,1);

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

   add(0 ,i ,pp[i]);

}

int Min_C ,Max_F;

void DFS(int s ,int t ,int ii ,int nowcost ,int n)

{

   if(ii == n3 + 1)

   {

      Rebuid(n);

      int now = DINIC(s ,t ,t);

      if(Max_F < now || Max_F == now && Min_C > nowcost)

      {

         Max_F = now;

         Min_C = nowcost;

      }

      return ;

   }

   mk[ii] = 1;

   DFS(s ,t ,ii + 1 ,nowcost + G[ii].c ,n);

   mk[ii] = 0;

   DFS(s ,t ,ii + 1 ,nowcost ,n);

}

int main ()

{

   int n ,m ,i ,q;

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

   {

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

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

      n1 = n2 = n3 = 0;

      NODE A;

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

      {

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

         if(q < 0) S[++n1] = A;

         if(!q)    L[++n2] = A;

         if(q > 0) G[++n3] = A;

      }

      Min_C = Max_F = 0;

      DFS(0 ,n + n1 + 1 ,1 ,0 ,n);

      if(!Max_F) puts("Poor Heaven Empire");

      else printf("%d %d\n" ,Max_F ,Min_C);

   }

   return 0;

}

巴特西

hdu 4309 最大流 + DFS

最新文章

热门文章