HDU4289 Control

　　原题传送：http://acm.hdu.edu.cn/showproblem.php?pid=4289

　　网络流，最大流 + 拆点。

　　最大流：sap算法

　　常用的两种拆点方式：

　　　　1. 对于每个节点id，拆成 id<<1 和 id<<1|1 两个点

　　　　2.对于每个节点id，拆成 id 和 id+n 两个点

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #define L(u) ((u) << 1)
  4 #define R(u) ((u) << 1 | 1)
  5 #define N 420
  6 #define M 100000
  7 #define INF 0x3f3f3f3f
  8 
  9 int gap[N],dis[N],pre[N],cur[N];
 10 int n,m,NE, s, t;
 11 int head[N];
 12 struct Node{
 13     int c,pos,next;
 14 }E[M];
 15 
 16 inline void checkmin(int &a,int b)  {if(a == -1 || a > b)a = b;}
 17 
 18 void add_edge(int u,int v,int c)
 19 {
 20     E[NE].c = c;
 21     E[NE].pos = v;
 22     E[NE].next = head[u];   
 23     head[u] = NE++;
 24     
 25     E[NE].c = 0;    // !反向初始为0
 26     E[NE].pos = u;
 27     E[NE].next = head[v];   
 28     head[v] = NE++;
 29 }
 30 
 31 int sap()
 32 {
 33     memset(dis,0,sizeof dis);
 34     memset(gap,0,sizeof gap);
 35     memcpy (cur, head, sizeof dis);
 36     int u=pre[s]=s,maxflow=0,aug=-1;
 37     gap[0]=n;
 38     while(dis[s]<n)
 39     {
 40 loop:for(int &i=cur[u];i!=-1;i=E[i].next)
 41         {
 42             int v=E[i].pos;
 43             if(E[i].c && dis[u]==dis[v]+1)
 44             {
 45                 checkmin(aug, E[i].c);
 46                 pre[v]=u;
 47                 u=v;
 48                 if(v==t)
 49                 {
 50                     maxflow+=aug;
 51                     for(u=pre[u];v!=s;v=u,u=pre[u])
 52                     {
 53                         E[cur[u]].c-=aug;
 54                         E[cur[u]^1].c+=aug;
 55                     }
 56                     aug=-1;
 57                 }
 58                 goto loop;
 59             }
 60         }
 61         int mindis=n;
 62         for(int i=head[u];i!=-1;i=E[i].next)
 63         {
 64             int v=E[i].pos;
 65             if(E[i].c && mindis>dis[v])
 66             {
 67                 cur[u]=i;
 68                 mindis=dis[v];
 69             }
 70         }
 71         if((--gap[dis[u]])==0) break;
 72         gap[dis[u]=mindis+1]++;
 73         u=pre[u];
 74     }
 75     return maxflow;
 76 }
 77  
 78 void init()
 79 {
 80     memset(head, -1, sizeof head);
 81     NE = 0;
 82 }
 83  
 84 int main()
 85 {
 86     int i, a, b, w;
 87     while(scanf("%d%d", &n, &m) != EOF)
 88     {
 89         init();
 90         scanf("%d%d", &s, &t);
 91         add_edge(0, L(s), INF);          // 0为超级源点
 92         add_edge(R(t), R(n + 1), INF);   // R(n + 1)为超级汇点
 93         s = 0;
 94         t = R(n + 1);
 95         for(i = 1; i <= n; i ++)
 96         {
 97             scanf("%d", &w);
 98             add_edge(L(i), R(i), w);
 99             add_edge(R(i), L(i), w); 
100         }
101         for(i = 0; i < m; i ++)
102         {
103             scanf("%d%d", &a, &b);
104             add_edge(R(a), L(b), INF);
105             add_edge(R(b), L(a), INF);
106         }
107         n = 2 * (n + 1);                 // 总节点数的变化
108         printf("%d\n", sap());
109     }
110     return 0;
111 }