笨笨的洪水堵截

背景
笨笨：汗……
路人甲：大汗……
笨笨：瀑布汗……
路人甲：大瀑布汗……
笨笨：懒得和你汗……
路人甲：怎么这么多水的啊？
描述
一场洪水即将到来，笨笨要想方设法堵截它！
堵截洪水的唯一办法是在洪水经过河流的岔道口放上石头！（笨笨在将小石头一颗一颗地垒好……囧）
对于不同的岔道口，需要的石头量不同，而笨笨所要消耗的体力也不同。
为了不太累，笨笨决定要用最少的体力来堵截这场洪水，洪水从岔道0出发，笨笨要防止洪水冲到岔道n。
格式
输入格式
输入有多组，输入第一行为组数（组数小于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之间有河道连接。
输出格式
对于每一组输入一个输出。
每组输入输出一行，表示笨笨所需要消耗的最小体力。
若洪水不可能冲到岔道n，则输出“Min!”，若洪水无法阻止，则输出“Max!”。
样例1
样例输入1
1
4 5
2 3 4
0 1
0 3
1 2
2 4
3 4
样例输出1
6
限制
1s
提示
对样例的解释：
洪水从0出发。
而笨笨要阻止洪水流到n。
耗体力最少的堵截方式就是将岔道1和岔道3堵上即可。
消耗体力最小总和为2+4=6。
来源
笨笨原创。

题面

解：
坑点1：要开long long,不然会挂两个点
坑点2：这是个无向图
建模方式：很明显的拆点
S=0;T=n;
i -> i+n 点权
如果x,与y之间有边 x+n -> y inf
注意源点和汇点的建边略有不同
如果Maxflow = 0 洪水不可能冲到岔道n
如果Maxflow>inf 洪水无法阻止
否则 Maxflow 即为笨笨所需要消耗的最小体力

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=1e5+10;
 5 struct node{
 6     ll v,fl,ne;
 7 }e[N];
 8 ll H[N],h[N],tot,n,m,S,T;
 9 void add1(ll u,ll v,ll fl)
10 {
11     tot++;e[tot]=(node){v,fl,h[u]};h[u]=tot;
12 }
13 void add(ll u,ll v,ll fl)
14 {
15     add1(u,v,fl);add1(v,u,0);
16 }
17 queue<ll>q;
18 ll d[N];
19 bool bfs()
20 {
21     for(ll i=0;i<=n*2;++i) d[i]=0;
22     d[S]=1;q.push(S);
23     while(!q.empty())
24     {
25         ll ff=q.front();q.pop();
26         for(ll i=h[ff],rr;i;i=e[i].ne)
27         {
28             rr=e[i].v;
29             if(!d[rr] && e[i].fl)
30              d[rr]=d[ff]+1,q.push(rr);
31         }
32     }
33     return d[T];
34 }
35 ll dfs(ll u,ll fl)
36 {
37     if(u==T || fl==0) return fl;
38     ll get=0,f;
39     for(ll i=H[u],rr;i;i=e[i].ne)
40     {
41         rr=e[i].v;
42         if(e[i].fl && d[rr]==d[u]+1)
43         {
44             f=dfs(rr,min(fl,e[i].fl));
45             if(f==0) continue;
46             get+=f;fl-=f;
47             e[i].fl-=f;e[i^1].fl+=f;
48             H[u]=i;
49             if(fl==0) break;
50         }
51     }
52     if(get==0) d[u]=0;
53     return get;
54 }
55 ll flow()
56 {
57     ll ans=0;
58     while(bfs())
59     {
60         for(ll i=0;i<=n*2;++i) H[i]=h[i];
61         ans+=dfs(S,1e9);
62     }
63     return ans;
64 }
65 ll fg,tt;
66 int main()
67 {
68     scanf("%lld",&tt);
69     while(tt--)
70     {
71         scanf("%lld%lld",&n,&m);
72         tot=1;for(ll i=0;i<=n*2;++i) h[i]=0; 
73         S=0;T=n;
74         for(ll i=1,x;i<=n-1;++i) 
75         {
76             scanf("%lld",&x);
77             add(i,i+n,x);
78         }
79         for(ll i=1,x,y;i<=m;++i)
80         {
81             scanf("%lld%lld",&x,&y);
82             if(x>y) swap(x,y);
83             if(x!=0)add(x+n,y,1e9),add(y+n,x,1e9);
84             else add(x,y,1e9),add(y+n,x,1e9);
85         }
86         fg=flow();
87         if(fg==0) puts("Min!");
88         else if(fg>1e9) puts("Max!");
89         else printf("%lld
",fg);
90     }
91     return 0;
92 }

代码