题解:
暴力枚举
然后网络流
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int E=,V=,inf=0xffff;
struct Edge{int u,v,c,next;}edge[E];
int a,bb,c,d,p[V],r,b,t,n,m,cnt,cou,dist[V],head[V],que[V],fb[],sta[V];
void init()
{
cnt=;
memset(head,-,sizeof(head));
}
void jb(int u,int v,int c)
{
edge[cnt].u=u;edge[cnt].v=v;edge[cnt].c=c;
edge[cnt].next=head[u];head[u]=cnt++;
edge[cnt].u=v;edge[cnt].v=u;edge[cnt].c=;
edge[cnt].next=head[v];head[v]=cnt++;
}
int dinic(int s,int t)
{
int ans=;
while()
{
int left,right,u,v;
memset(dist,-,sizeof(dist));
left=right=;
que[right++]=s;
dist[s]=;
while (left<right)
{
u=que[left++];
for (int k=head[u];k!=-;k=edge[k].next)
{
u=edge[k].u;
v=edge[k].v;
if (edge[k].c> && dist[v]==-)
{
dist[v]=dist[u]+;
que[right++]=v;
if(v==t)
{
left=right;
break;
}
}
}
}
if (dist[t]==-) break;
int top=,now=s;
while ()
{
if (now!=t)
{
int k;
for (k=head[now];k!=-;k=edge[k].next)
if (edge[k].c>&&dist[edge[k].u]+==dist[edge[k].v]) break;
if (k!=-)
{
sta[top++]=k;
now=edge[k].v;
}
else
{
if (top==) break;
dist[edge[sta[--top]].v]=-;
now=edge[sta[top]].u;
}
}
else
{
int flow=inf,ebreak;
for (int i=;i<top;i++)
if (flow>edge[sta[i]].c)
{
flow=edge[sta[i]].c;
ebreak=i;
}
ans+=flow;
for (int i=;i<top;i++)
{
edge[sta[i]].c-=flow;
edge[sta[i]^].c+=flow;
}
now=edge[sta[ebreak]].u;
top=ebreak;
}
}
}
return ans;
}
struct T{int u,v,c;}road[E],bridge[E],tunnel[E];
struct R{int num,cost;}res[E];
void build()
{
init();
for (int i=;i<=n;i++)jb(,i,p[i]);
for (int i=;i<r;i++)jb(road[i].u,road[i].v,inf);
for (int i=;i<t;i++)
{
jb(tunnel[i].u,n+i+,inf);
jb(n+i+,tunnel[i].v,inf);
jb(n+i+,n+t+,tunnel[i].c);
}
}
void dfs(int s)
{
if (s==b)
{
int sum=;
build();
for (int i=;i<b;i++)
{
if (fb[i]==)
{
jb(bridge[i].u,bridge[i].v,);
sum+=;
}
else
{
jb(bridge[i].u,bridge[i].v,inf);
sum+=bridge[i].c;
}
}
res[cou].num=dinic(,n+t+);
res[cou++].cost=sum;
return ;
}
fb[s]=;
dfs(s+);
fb[s]=;
dfs(s+);
}
int main()
{
while (~scanf("%d%d",&n,&m))
{
for (int i=;i<=n;i++)scanf("%d",&p[i]);
r=b=t=;
for (int i=;i<=m;i++)
{
scanf("%d%d%d%d",&a,&bb,&c,&d);
if (d<)
{
tunnel[t].u=a;
tunnel[t].v=bb;
tunnel[t++].c=c;
}
if (d==)
{
road[r].u=a;
road[r++].v=bb;
}
if (d>)
{
bridge[b].u=a;
bridge[b].v=bb;
bridge[b++].c=c;
}
}
memset(fb,,sizeof(fb));
for (int i=;i<;i++)res[i].cost=res[i].num=;
cou=;dfs();
int minc=inf,maxc=-;
for (int i=;i<cou;i++)
if (res[i].num>maxc)maxc=res[i].num;
for (int i=;i<cou;i++)
if (res[i].num==maxc)
if (res[i].cost<minc)minc=res[i].cost;
if (maxc==) puts("Poor Heaven Empire");
else printf("%d %d\n",maxc,minc);
}
return ;
}