HDU 4309 Seikimatsu Occult Tonneru（最大流+二进制枚举）

http://acm.hdu.edu.cn/showproblem.php?pid=4309

题意：

有n个城市，每个城市有num[i]个居民，有敌人要进行地毯式轰击，居民们要逃到隧道去。现在有隧道，隧道允许无限个人通过，并且可以容纳w个人；有桥，可以允许无限个人通过，但是不能容纳人；还有一些破桥，修复这些破桥需要w花费，如果不修复，那么最多只能通过一人，如果修复了，那么可以通过无限个人。求出在能安全到达隧道的最大人数时的最小代价。（上述都是单向边）

思路：
出题人也是有心了。。在题目中有说破桥的名字是用十二星座命名的，也就是说，破桥最多只有12座，既然这样，完全就可以二进制枚举了。

建立超级源点，源点向每个城市连边，容量为城市人数；隧道连u->v的容量为inf的边，并且连u->T的容量为w的边，桥连u->v的容量为inf的边。破桥就是二进制枚举修复的情况。多次求最大流即可。

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<sstream>
  6 #include<vector>
  7 #include<stack>
  8 #include<queue>
  9 #include<cmath>
 10 #include<map>
 11 #include<set>
 12 using namespace std;
 13 typedef long long ll;
 14 typedef long long ull;
 15 typedef pair<int,int> pll;
 16 const int INF = 0x3f3f3f3f;
 17 const int maxn = 100 + 5;
 18 
 19 int num[maxn];
 20 
 21 struct node
 22 {
 23     int u,v,w,p;
 24     node(int u, int v, int w, int p):u(u),v(v),w(w),p(p){}
 25 };
 26 
 27 vector<node> vec[3];
 28 
 29 struct Edge
 30 {
 31     int from,to,cap,flow;
 32     Edge(int u,int v,int w,int f):from(u),to(v),cap(w),flow(f){}
 33 };
 34 
 35 struct Dinic
 36 {
 37     int n,m,s,t;
 38     vector<Edge> edges;
 39     vector<int> G[maxn];
 40     bool vis[maxn];
 41     int cur[maxn];
 42     int d[maxn];
 43 
 44     void init(int n)
 45     {
 46         this->n=n;
 47         for(int i=0;i<n;++i) G[i].clear();
 48         edges.clear();
 49     }
 50 
 51     void AddEdge(int from,int to,int cap)
 52     {
 53         edges.push_back( Edge(from,to,cap,0) );
 54         edges.push_back( Edge(to,from,0,0) );
 55         m=edges.size();
 56         G[from].push_back(m-2);
 57         G[to].push_back(m-1);
 58     }
 59 
 60     bool BFS()
 61     {
 62         queue<int> Q;
 63         memset(vis,0,sizeof(vis));
 64         vis[s]=true;
 65         d[s]=0;
 66         Q.push(s);
 67         while(!Q.empty())
 68         {
 69             int x=Q.front(); Q.pop();
 70             for(int i=0;i<G[x].size();++i)
 71             {
 72                 Edge& e=edges[G[x][i]];
 73                 if(!vis[e.to] && e.cap>e.flow)
 74                 {
 75                     vis[e.to]=true;
 76                     d[e.to]=d[x]+1;
 77                     Q.push(e.to);
 78                 }
 79             }
 80         }
 81         return vis[t];
 82     }
 83 
 84     int DFS(int x,int a)
 85     {
 86         if(x==t || a==0) return a;
 87         int flow=0, f;
 88         for(int &i=cur[x];i<G[x].size();++i)
 89         {
 90             Edge &e=edges[G[x][i]];
 91             if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0)
 92             {
 93                 e.flow +=f;
 94                 edges[G[x][i]^1].flow -=f;
 95                 flow +=f;
 96                 a -=f;
 97                 if(a==0) break;
 98             }
 99         }
100         return flow;
101     }
102 
103     int Maxflow(int s,int t)
104     {
105         this->s=s; this->t=t;
106         int flow=0;
107         while(BFS())
108         {
109             memset(cur,0,sizeof(cur));
110             flow +=DFS(s,INF);
111         }
112         return flow;
113     }
114 }DC;
115 
116 int n,m;
117 
118 int main()
119 {
120     //freopen("in.txt","r",stdin);
121     while(~scanf("%d%d",&n,&m))
122     {
123         vec[0].clear(); vec[1].clear(); vec[2].clear();
124         for(int i=1;i<=n;i++)  scanf("%d",&num[i]);
125         for(int i=1;i<=m;i++)
126         {
127             int u,v,w,p;
128             scanf("%d%d%d%d",&u,&v,&w,&p);
129             if(p<0)  vec[0].push_back(node(u,v,w,p));
130             else if(p==0)  vec[1].push_back(node(u,v,w,p));
131             else vec[2].push_back(node(u,v,w,p));
132         }
133         int people = -1, cost = INF;
134         int tunnel = vec[0].size();
135         if(tunnel == 0)  {puts("Poor Heaven Empire");continue;}
136         int bridge = vec[2].size();
137         int src = 0, dst = n+1;
138         for(int state=0;state<(1<<bridge);state++)
139         {
140             int tmp = 0;
141             DC.init(dst+1);
142             for(int i=1;i<=n;i++)  DC.AddEdge(src,i,num[i]);
143             for(int i=0;i<vec[0].size();i++)
144             {
145                 node p = vec[0][i];
146                 DC.AddEdge(p.u,p.v,INF);
147                 DC.AddEdge(p.u,dst,p.w);
148             }
149             for(int i=0;i<vec[1].size();i++)
150             {
151                 node p = vec[1][i];
152                 DC.AddEdge(p.u, p.v, INF);
153             }
154             for(int i=0;i<vec[2].size();i++)
155             {
156                 node p = vec[2][i];
157                 if((1<<i)&state)
158                 {
159                     tmp += p.w;
160                     DC.AddEdge(p.u, p.v, INF);
161                 }
162                 else
163                 {
164                     DC.AddEdge(p.u, p.v, 1);
165                 }
166             }
167             int flow = DC.Maxflow(src,dst);
168             if(flow == people)  cost = min(cost,tmp);
169             if(flow > people)
170             {
171                 people = flow;
172                 cost = tmp;
173             }
174         }
175         if(people == -1)  puts("Poor Heaven Empire");
176         else printf("%d %d
",people,cost);
177     }
178     return 0;
179 }