HDU 4309 Seikimatsu Occult Tonneru

Seikimatsu Occult Tonneru

Time Limit: 6000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 4309
64-bit integer IO format: %I64d Java class name: Main

During the world war, to avoid the upcoming Carpet-bombing from The Third Reich, people in Heaven Empire went to Great Tunnels for sheltering.
There are N cities in Heaven Empire, where people live, with 3 kinds of directed edges connected with each other. The 1st kind of edges is one of Great Tunnels( no more than 20 tunnels) where a certain number of people can hide here; people can also go through one tunnel from one city to another. The 2nd kind of edges is the so-called Modern Road, which can only let people go through. The 3rd kind of edges is called Ancient Bridge and all the edges of this kind have different names from others, each of which is named with one of the twelve constellations( such as Libra, Leo and so on); as they were build so long time ago, they can be easily damaged by one person's pass. Well, for each bridge, you can spend a certain deal of money to fix it. Once repaired, the 3rd kind of edges can let people pass without any limitation, namely, you can use one bridge to transport countless people. As for the former two kinds of edges, people can initially go through them without any limitation.
We want to shelter the most people with the least money.
Now please tell me the largest number of people who can hide in the Tunnels and the least money we need to spend to realize our objective.

Input

Multiple Cases.
The first line, two integers: N (N<=100), m (m<=1000). They stands for the number of cities and edges.
The next line, N integers, which represent the number of people in the N cities.
Then m lines, four intergers each: u, v, w, p (1<=u, v<=N, 0<=w<=50). A directed edge u to v, with p indicating the type of the edge: if it is a Tunnel then p < 0 and w means the maximum number people who can hide in the the tunnel; if p == 0 then it is a Modern Road with w means nothing; otherwise it is an Ancient Bridge with w representing the cost of fixing the bridge. We promise there are no more than one edge from u to v.

Output

If nobody can hide in the Tunnels, print “Poor Heaven Empire”, else print two integers: maximum number and minimum cost.

Sample Input

Sample Output

4 0
4 3

Source

2012 Multi-University Training Contest 1

解题：暴力枚举+拆边最大流

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <climits>
  7 #include <vector>
  8 #include <queue>
  9 #include <cstdlib>
 10 #include <string>
 11 #include <set>
 12 #include <stack>
 13 #define LL long long
 14 #define pii pair<int,int>
 15 #define INF 0x3f3f3f3f
 16 using namespace std;
 17 const int maxn = 3000;
 18 struct arc{
 19     int to,flow,next;
 20     arc(int x = 0,int y = 0,int z = -1){
 21         to = x;
 22         flow = y;
 23         next = z;
 24     }
 25 };
 26 arc e[maxn*20],tmpe[maxn*20];
 27 int head[maxn],d[maxn],cur[maxn];
 28 int tot,S,T,n,m,cnt,p[maxn];
 29 pii rec[maxn*20];
 30 void add(int u,int v,int flow){
 31     e[tot] = arc(v,flow,head[u]);
 32     head[u] = tot++;
 33     e[tot] = arc(u,0,head[v]);
 34     head[v] = tot++;
 35 }
 36 bool bfs(){
 37     memset(d,-1,sizeof(d));
 38     queue<int>q;
 39     d[T] = 1;
 40     q.push(T);
 41     while(!q.empty()){
 42         int u = q.front();
 43         q.pop();
 44         for(int i = head[u]; ~i; i = e[i].next){
 45             if(e[i^1].flow && d[e[i].to] == -1){
 46                 d[e[i].to] = d[u] + 1;
 47                 q.push(e[i].to);
 48             }
 49         }
 50     }
 51     return d[S] > -1;
 52 }
 53 int dfs(int u,int low){
 54     if(u == T) return low;
 55     int tmp = 0,a;
 56     for(int &i = cur[u]; ~i; i = e[i].next){
 57         if(e[i].flow && d[u] == d[e[i].to]+1&&(a=dfs(e[i].to,min(low,e[i].flow)))){
 58             e[i].flow -= a;
 59             e[i^1].flow += a;
 60             low -= a;
 61             tmp += a;
 62             if(!low) break;
 63         }
 64     }
 65     if(!tmp) d[u] = -1;
 66     return tmp;
 67 }
 68 int dinic(){
 69     int ans = 0;
 70     while(bfs()){
 71         memcpy(cur,head,sizeof(head));
 72         ans += dfs(S,INF);
 73     }
 74     return ans;
 75 }
 76 int main() {
 77     int u,v,w,type;
 78     while(~scanf("%d %d",&n,&m)){
 79         memset(head,-1,sizeof(head));
 80         S = tot =  0;
 81         T = n+m+1;
 82         for(int i = 1; i <= n; ++i){
 83             scanf("%d",&w);
 84             add(S,i,w);
 85         }
 86         int o = n + 1;
 87         for(int i = cnt = 0; i < m; ++i){
 88             scanf("%d %d %d %d",&u,&v,&w,&type);
 89             if(type == 0) add(u,v,INF);
 90             else if(type < 0){
 91                 add(u,o,INF);
 92                 add(o,v,INF);
 93                 add(o++,T,w);
 94             }else{
 95                 rec[cnt++] = make_pair(tot,w);
 96                 add(u,v,1);
 97             }
 98         }
 99         int st = 1<<cnt,ans = 0,cost = INF;
100         memcpy(tmpe,e,sizeof(e));
101         for(int i = 0; i < st; ++i){
102             int tp = 0,tc = 0;
103             memcpy(e,tmpe,sizeof(e));
104             for(int k = 0; k < cnt; ++k){
105                 if(i&(1<<k)){
106                     tc += rec[k].second;
107                     e[rec[k].first].flow = INF;
108                 }
109             }
110             tp = dinic();
111             if(tp > ans){
112                 ans = tp;
113                 cost = tc;
114             }else if(tp == ans && cost > tc) cost = tc;
115         }
116         if(ans == 0) puts("Poor Heaven Empire");
117         else printf("%d %d
",ans,cost);
118     }
119     return 0;
120 }

View Code