hdu4289最小割

最近博客断更了一段时间啊，快期末了，先把这个专题搞完再说

最小割=最大流

拆点方法很重要，刚开始我拆点不对就wa了，然后改进后tle，应该是数组开小了，一改果然是

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 100000000
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define MIN(a,b) a<b ? a:b

using namespace std;

const double g=10.0,eps=1e-9;
const int N=20000+10,maxn=500+10,inf=10000000;

struct edge{
   int to,next,cap;
}e[N<<2];
int head[maxn],dis[maxn];
int cnt,s,t;
void add(int u,int v,int c)
{
   e[cnt].to=v;
   e[cnt].cap=c;
   e[cnt].next=head[u];
   head[u]=cnt++;
   e[cnt].to=u;
   e[cnt].cap=0;
   e[cnt].next=head[v];
   head[v]=cnt++;
}
bool bfs()
{
    queue<int>q;
    q.push(s);
    memset(dis,-1,sizeof dis);
    dis[s]=0;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int p=e[i].to;
            if(dis[p]==-1&&e[i].cap>0)
            {
                dis[p]=dis[x]+1;
             //   cout<<p<<" "<<dis[p]<<endl;
                q.push(p);
            }
        }
    }
  //  cout<<dis[t];
    return dis[t]>-1;
}
int dfs(int x,int mx)
{
    if(x==t)return mx;
    for(int i=head[x];i!=-1;i=e[i].next)
    {
        int p=e[i].to,f;
        if(dis[p]==dis[x]+1&&e[i].cap>0&&(f=dfs(p,min(e[i].cap,mx))))
        {
            e[i].cap-=f;
            e[i^1].cap+=f;
            return f;
        }
    }
    dis[x]=-2;
    return 0;
}
int max_flow()
{
    int flow=0,p;
    while(bfs()){
        while((p=dfs(s,inf)))flow+=p;
    }
    return flow;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    while(cin>>n>>m){
        cin>>s>>t;
        t+=n;
        int a,b;
        cnt=0;
        memset(head,-1,sizeof head);
        for(int i=1;i<=n;i++)
        {
            cin>>a;
            add(i,i+n,a);
        }
        while(m--){
            cin>>a>>b;
            add(a+n,b,inf);
            add(b+n,a,inf);
        }
        int ans=max_flow();
        cout<<ans<<endl;
    }
    return 0;
}