hdu4971 流-最大权闭包

最后答案是 所有任务的价值 - maxflow

#include<stdio.h>
#include<string.h>
#include<queue>

#define N_node 100
#define N_edge 8000
#define INF 1000000000

using namespace std;

typedef struct
{
   int to ,next ,cost;
}STAR;

typedef struct
{
   int x ,t;
}DEP;

STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int deep[N_node];

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

bool BFS_Deep(int s ,int t ,int n)
{
   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 ++)
    listt[i] = list[i];
    return deep[t] != -1;
}

int minn(int x ,int y)
{
    return x < y ? x : y;
}

int DFS_Flow(int s ,int t ,int flow)
{
    if(s == t) return flow;
    int nowflow = 0;
    for(int k = listt[s] ;k ;k = E[k].next)
    {
       listt[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(nowflow == flow) 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;
}

int main ()
{
    int i ,j ,n ,nn ,m ,a ,T ,cas = 1;
    int s ,t ,sum_z;
    scanf("%d" ,&T);
    while(T--)
    {
       scanf("%d %d" ,&n ,&m);
       s = 0 ,t = n + m + 1;
       memset(list ,0 ,sizeof(list)) ,tot = 1;
       for(sum_z = 0 ,i = 1 ;i <= n ;i ++)
       {
          scanf("%d" ,&a);
          sum_z += a;
          add(s ,i ,a);
       }
       for(i = 1 ;i <= m ;i ++)
       {
          scanf("%d" ,&a);
          add(i + n ,t ,a);
       }
       for(i = 1 ;i <= n ;i ++)
       {
          scanf("%d" ,&nn);
          while(nn--)
          {
              scanf("%d" ,&a);
              a ++;
              add(i ,a + n ,INF);
          }
       }
       for(i = 1 ;i <= m ;i ++)
       for(j = 1 ;j <= m ;j ++)
       {
          scanf("%d" ,&a);
          if(a) add(i + n ,j + n ,INF);
       }
       printf("Case #%d: " ,cas ++);
       printf("%d\n" ,sum_z - DINIC(s ,t ,t));
    }
    return 0;
}