1 /*************************************  2 *ACM Solutions  3 *@Author: xysmlx  4 *@Blog: http://www.cnblogs.com/xysmlx  5 *************************************/  6 // #pragma comment(linker, "/STACK:102400000,102400000")  7 #include <cstdio>  8 #include <iostream>  9 #include <cstring> 10 #include <string> 11 #include <cmath> 12 #include <set> 13 #include <list> 14 #include <map> 15 #include <iterator> 16 #include <cstdlib> 17 #include <vector> 18 #include <queue> 19 #include <stack> 20 #include <algorithm> 21 #include <functional> 22 using namespace std; 23 typedef long long LL; 24 #define pb push_back 25 #define ROUND(x) round(x) 26 #define FLOOR(x) floor(x) 27 #define CEIL(x) ceil(x) 28 // const int maxn = 0; 29 // const int maxm = 0; 30 // const int inf = 0x3f3f3f3f; 31 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 32 const double INF = 1e30; 33 const double eps = 1e-6; 34 const int P[4] = {0, 0, -1, 1}; 35 const int Q[4] = {1, -1, 0, 0}; 36 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 37 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 38  39 /** 40 *最大流最小割：加各种优化的Dinic算法($O(V^2E)$) 41 *输入：图(链式前向星),n(顶点个数,包含源汇),st(源),ed(汇) 42 *输出：Dinic(NdFlow)(最大流),MinCut()(最小割)(需先求最大流) 43 *打印路径方法：按反向边(i&1)的flow 找，或者按边的flow找 44 */ 45 const int maxn = 510; 46 const int maxm = 20010; 47 const int inf = 0x3f3f3f3f; 48 struct DINIC 49 { 50     struct Edge 51     { 52         int u, v; 53         int cap, flow; 54         int next; 55     } edge[maxm]; 56     int head[maxn], en; //需初始化 57     int n, m, d[maxn], cur[maxn]; 58     int st, ed; 59     bool vis[maxn]; 60     void init(int _n = 0) 61     { 62         n = _n; 63         memset(head, -1, sizeof(head)); 64         en = 0; 65     } 66     void addse(int u, int v, int cap, int flow) 67     { 68         edge[en].u = u; 69         edge[en].v = v; 70         edge[en].cap = cap; 71         edge[en].flow = flow; 72         edge[en].next = head[u]; 73         head[u] = en++; 74         cur[u] = head[u]; 75     } 76     void adde(int u, int v, int cap) 77     { 78         addse(u, v, cap, 0); 79         addse(v, u, 0, 0); //注意加反向0 边 80     } 81     bool BFS() 82     { 83         queue<int> Q; 84         memset(vis, 0, sizeof(vis)); 85         Q.push(st); 86         d[st] = 0; 87         vis[st] = 1; 88         while (!Q.empty()) 89         { 90             int u = Q.front(); 91             Q.pop(); 92             for (int i = head[u]; i != -1; i = edge[i].next) 93             { 94                 int v = edge[i].v; 95                 int w = edge[i].cap - edge[i].flow; 96                 if (w > 0 && !vis[v]) 97                 { 98                     vis[v] = 1; 99                     Q.push(v);100                     d[v] = d[u] + 1;101                     if (v == ed) return 1;102                 }103             }104         }105         return false;106     }107     int Aug(int u, int a)108     {109         if (u == ed) return a;110         int aug = 0, delta;111         for (int &i = cur[u]; i != -1; i = edge[i].next)112         {113             int v = edge[i].v;114             int w = edge[i].cap - edge[i].flow;115             if (w > 0 && d[v] == d[u] + 1)116             {117                 delta = Aug(v, min(a, w));118                 if (delta)119                 {120                     edge[i].flow += delta;121                     edge[i ^ 1].flow -= delta;122                     aug += delta;123                     if (!(a -= delta)) break;124                 }125             }126         }127         if (!aug) d[u] = -1;128         return aug;129     }130     int Dinic(int NdFlow)131     {132         int flow = 0;133         while (BFS())134         {135             memcpy(cur, head, sizeof(int) * (n + 1));136             flow += Aug(st, inf);137             /*如果超过指定流量就return 掉*/138             if (NdFlow == inf) continue;139             if (flow > NdFlow) break;140         }141         return flow;142     }143     /*残余网络*/144     void Reduce()145     {146         for (int i = 0; i < en; i++) edge[i].cap -= edge[i].flow;147     }148     /*清空流量*/149     void ClearFlow()150     {151         for (int i = 0; i < en; i++) edge[i].flow = 0;152     }153     /*求最小割*/154     vector<int> MinCut()155     {156         BFS();157         vector<int> ans;158         for (int u = 0; u < n; u++)159         {160             if (!vis[u]) continue;161             for (int i = head[u]; i != -1; i = edge[i].next)162             {163                 if (i & 1) continue; /*忽略反向边*/164                 int v = edge[i].v;165                 int w = edge[i].cap;166                 if (!vis[v] && w > 0) ans.push_back(i);167             }168         }169         return ans;170     }171 } dinic;172 173 int kase;174 int n, m;175 int a[maxn];176 int cost;177 int flow;178 int tcost;179 struct Edge180 {181     int u, v;182     int w;183     int p;184     int flag;185     Edge(int _u, int _v, int _w, int _p): u(_u), v(_v), w(_w), p(_p) {}186     Edge() {}187 };188 vector<Edge> e;189 vector<int> rec;190 void init()191 {192     kase++;193     e.clear();194     rec.clear();195     flow = 0;196     cost = inf;197 }198 void input()199 {200     for (int i = 0; i < n; i++)201         scanf("%d", &a[i]);202     for (int i = 0; i < m; i++)203     {204         int u, v, w, p;205         scanf("%d%d%d%d", &u, &v, &w, &p);206         u--, v--;207         e.pb(Edge(u, v, w, p));208         e[i].flag = 0;209         if (p > 0) rec.pb(i);210     }211 }212 void debug()213 {214     //215 }216 void build()217 {218     dinic.init(n + 2);219     dinic.st = 0;220     dinic.ed = 1;221     for (int i = 0; i < n; i++)222         dinic.adde(dinic.st, i + 2, a[i]);223     for (int i = 0; i < m; i++)224     {225         int u = e[i].u;226         int v = e[i].v;227         int w = e[i].w;228         int p = e[i].p;229         if (p < 0)230         {231             dinic.adde(u + 2, v + 2, inf);232             dinic.adde(u + 2, dinic.ed, w);233         }234         else if (p == 0) dinic.adde(u + 2, v + 2, inf);235         else236         {237             if (e[i].flag) dinic.adde(u + 2, v + 2, inf);238             else dinic.adde(u + 2, v + 2, 1);239         }240     }241 }242 void cal()243 {244     build();245     int tmp = dinic.Dinic(inf);246     if (tmp > flow)247     {248         flow = tmp;249         cost = tcost;250     }251 }252 void solve()253 {254     for (int i = 0; i < (1 << rec.size()); i++)255     {256         tcost = 0;257         for (int j = 0; j < rec.size(); j++)258             if (i & (1 << j)) e[rec[j]].flag = 1, tcost += e[rec[j]].w;259         cal();260         for (int j = 0; j < rec.size(); j++)261             if (i & (1 << j)) e[rec[j]].flag = 0;262     }263 }264 void output()265 {266     cost = cost == inf ? 0 : cost;267     if (flow == 0) puts("Poor Heaven Empire");268     else printf("%d %d\n", flow, cost);269 }270 int main()271 {272     // int size = 256 << 20; // 256MB273     // char *p = (char *)malloc(size) + size;274     // __asm__("movl %0, %%esp\n" :: "r"(p));275 276     // std::ios_base::sync_with_stdio(false);277 #ifdef xysmlx278     freopen("in.cpp", "r", stdin);279 #endif280 281     kase = 0;282     while (~scanf("%d%d", &n, &m))283     {284         init();285         input();286         solve();287         output();288     }289     return 0;290 }