背景 Background
笨笨：汗……
路人甲：大汗……
笨笨：瀑布汗……
路人甲：大瀑布汗……
笨笨：懒得和你汗……
路人甲：怎么这么多水的啊？
描述 Description
一场洪水即将到来，笨笨要想方设法堵截它！
堵截洪水的唯一办法是在洪水经过河流的岔道口放上石头！（笨笨在将小石头一颗一颗地磊好……囧）
对于不同的岔道口，需要的石头量不同，而笨笨所要消耗的体力也不同。
为了不太累，笨笨决定要用最少的体力来堵截这场洪水，洪水从岔道0出发，笨笨要防止洪水冲到岔道n。
输入格式 Input Format
输入有多组，输入第一行为组数（组数小于15）。
每组输入格式如下。
第一行两个数n,m（0<n<=50,0<=m<=200）。
第二行n-1个数，第i个数表示堵截该岔道需要消耗笨笨k[i]的体力。(i=1 to n-1，每个k[i]都是正整数)
接下来m行，每行两个数a,b，表示岔道a和岔道b之间有河道连接。
输出格式 Output Format
对于每一组输入一个输出。
每组输入输出一行，表示笨笨所需要消耗的最小体力。
若洪水不可能冲到岔道n，则输出“Min!”，若洪水无法阻止，则输出“Max!”。
样例输入 Sample Input
1
4 5
2 3 4
0 1
0 3
1 2
2 4
3 4
样例输出 Sample Output
6
时间限制 Time Limitation
1s
注释 Hint
对样例的解释：
洪水从0出发。
而笨笨要阻止洪水流到n。
耗体力最少的堵截方式就是将岔道1和岔道3堵上即可。
消耗体力最小总和为2+4=6。
【参考程序】：
#include<cstring>
#include<cstdio>
#define maxint 0x7FFFFFFF
using namespace std;
int g[210][210],queue[210],prev[210];
bool vis[210];
int n,m,ans;
bool bfs_path()
{
memset(vis,false,sizeof(vis));
memset(prev,0,sizeof(prev));
int head,tail,now;
head=tail=1;
queue[1]=0; vis[0]=true;
while (head<=tail)
{
now=queue[head];
for (int i=1;i<=2*n+1;i++)
if (!vis[i] && g[now][i])
{
vis[i]=true;
tail++;
queue[tail]=i; prev[i]=now;
if (i==n) return true;
}
head++;
}
return false;
}
int main()
{
int a,b,T,bk;
scanf("%d",&T);
for (int t=1;t<=T;t++)
{
scanf("%d%d",&n,&m);
if (n==0)
{
printf("Max!\n"); continue;
}
memset(g,0,sizeof(g));
for (int i=1;i<n;i++) scanf("%d",&g[n+1+i][i]);
bk=1;
for (int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if ((a==0 && b==n)||(a==n && b==0)) bk=0;
a g[a][n+1+b]=g[b][n+1+a]=maxint;
}
g[n+1+n][n]=maxint;
if (!bk)
{
printf("Max!\n");continue;
}
ans=0;
while (bfs_path())
{
int flow=maxint,i;
i=n;
while (i!=0)
{
if (flow>g[prev[i]][i]) flow=g[prev[i]][i];
i=prev[i];
}
ans+=flow;
i=n;
while (i!=0)
{
g[prev[i]][i]-=flow;
if (g[i][prev[i]]+flow<=maxint)
g[i][prev[i]]+=flow;
else g[i][prev[i]]=maxint;
i=prev[i];
}
}
if (ans==0) printf("Min!\n");
else printf("%d\n",ans);
}
return 0;
}