HDU 1569 方格取数(2)(最大点权独立集：最大流)-白红宇

HDU 1569 方格取数(2)(最大点权独立集：最大流)

阅读量：5111 次

发布时间：2019-06-13

本文共 4801 字，大约阅读时间需要 16 分钟。

【题意】：略

【分析】：

黑白棋盘，转化为二分图。

1、最大点权独立集 = sum - 最小点权覆盖集

2、最小点权覆盖集 = 最小割 = 最大流

3、贴了个dinic模板

【Mark】:开刷网络流《最小割模型在信息学竞赛中的应用》

1 /***  2 Author:wangsouc  3   4 ***/  5   6 #include
      
         7 #include
       
          8 #include
        
           9 #define MAX_EDGE 250500 10 #define MAX_VECT 2555 11 #define INF 1000000 12 #include
         
           13 using namespace std; 14  15 int to[MAX_EDGE], next[MAX_EDGE], cap[MAX_EDGE], m; 16 int v[MAX_VECT], d[MAX_VECT], queue[MAX_VECT], n; 17 int S, T; 18 inline void single_insert(int _u, int _v, int var) 19 { 20     to[m] = _v; 21     cap[m] = var; 22     next[m] = v[_u]; 23     v[_u] = m++; 24 } 25  26 void insert(int from, int to,  int cap) 27 { 28     single_insert(from, to, cap); 29     single_insert(to, from, 0); 30 } 31  32 bool bfs_initial() 33 { 34     memset(d, -1, sizeof(d)); 35     int bg, ed, x, y; 36     bg = ed = d[S] = 0; 37     queue[ed++] = S; 38     while (bg < ed) 39     { 40         x = queue[bg++]; 41         for (int i = v[x]; i+1; i = next[i]) 42         { 43             y = to[i]; 44             if (cap[i] && d[y] == -1) 45             { 46                 d[y] = d[x] + 1; 47                 if (y == T) return true; 48                 queue[ed++] = y; 49             } 50         } 51     } 52     return false; 53 } 54  55 int Find(int x, int low = INF) 56 { 57     if (x == T) return low; 58     int ret, y, ans = 0; 59     for (int i = v[x]; (i+1) && low; i = next[i]) 60     { 61         y = to[i]; 62         if (cap[i] && d[y] == d[x] + 1 && (ret = Find(y, min(low, cap[i])))) 63         { 64             cap[i] -= ret; 65             cap[i^1] += ret; 66             low -= ret; 67             ans += ret; 68         } 69     } 70     return ans; 71 } 72  73 int dinic() 74 { 75     int ans = 0; 76     while (bfs_initial()) 77         ans += Find(S); 78     return ans; 79 } 80 int dinicc() 81 { 82     int ans = 0; 83     while(bfs_initial()) 84     { 85         int edge, x, y, back, iter = 1; 86         while(iter) 87         { 88             x = (iter == 1) ? S : to[queue[iter - 1]]; 89             if (x == T) 90             { 91                 int minE, minCap = INF; 92                 for (int i = 1; i < iter; i++) 93                 { 94                     edge = queue[i]; 95                     if (cap[edge] < minCap) 96                     { 97                         minCap = cap[edge]; 98                         back = i; 99                     }100                 }101                 for (int i = 1; i < iter; i++)102                 {103                     edge = queue[i];104                     cap[edge] -= minCap;105                     cap[edge ^ 1] += minCap;106                 }107                 ans += minCap;108                 iter = back;109             }110             else111             {112                 for (edge = v[x]; edge + 1; edge = next[edge])113                 {114                     y = to[edge];115                     if (cap[edge] && d[y] == d[x] + 1)116                         break;117                 }118                 if (edge+1)119                     queue[iter++] = edge;120                 else121                 {122                     d[x] = -1;123                     iter--;124                 }125             }126         }127     }128     return ans;129 }130 int check(int x,int y,int a,int b)131 {132     if (x>=1 && x<=a &&y>=1 && y<=b)133     {134         if ((x + y)%2 == 1)135             return (x-1)*b + y;136     }137     return 0;138 }139 int dir[4][2]= {
    {-1,0},{
    0,1},{
    1,0},{
    0,-1}};140 int main()141 {142     int a,b;143     while (scanf("%d%d",&a,&b)==2)144     {145         int sum = 0;146         memset(v,-1,sizeof(v));147         m = 0;148         S = 0;149         T = a*b + 1;150         for (int i=1; i<=a; i++)151             for (int j=1; j<=b; j++)152             {153                 int x;154                 scanf("%d",&x);155                 sum += x;156                 int now = (i-1)*b + j;157                 if ((i+j) % 2 == 0)158                 {159                     insert(S,now,x);160                     for (int k=0; k<4; k++)161                     {162                         int cur = check(i+dir[k][0],j+dir[k][1],a,b);163                         if (cur>0)164                         {165                             insert(now,cur,INF);166                         }167                     }168                 }169                 else170                 {171                     insert(now,T,x);172                 }173 174             }175         int ret = dinic();176         printf("%d\n",sum - ret);177     }178     return 0;179 }