Bakser's Blog

我是逗比。

bzoj2163 最大流

| Comments

可以看11年陈许旻作业.
我写的是算法5,就是最大流.
吐句槽,网络流的复杂度不要信啊.

bzoj2163
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
#define N 20100
#define M 300000
#define MIN(a,b) (((a)<(b))?(a):(b))
#define INF 0x3f3f3f3f
struct hh
{
    int u,v,next,cap;
}edges[M];
int n,m,f[N>>1],point[N],num,s,t,sum,cur[N],p[N],gap[N],d[N];
inline void addedge(int u,int v,int w)
{
    static int en(-1);
    edges[++en].next=point[u];edges[en].u=u;edges[en].v=v;
    edges[en].cap=w;point[u]=en;
    edges[++en].next=point[v];edges[en].u=v;edges[en].v=u;
    edges[en].cap=0;point[v]=en;
}
inline void bfs()
{
    static queue<int> q;
    memset(d,0xff,sizeof(d));
    gap[d[t]=0]++;
    q.push(t);
    while(!q.empty())
    {
        int x(q.front());q.pop();
        for(int i=point[x];i!=-1;i=edges[i].next)
        if(edges[i^1].cap&&d[edges[i^1].u]==-1)
        {
            gap[d[edges[i^1].u]=d[x]+1]++;
            q.push(edges[i^1].u);
        }
    }
}
inline int augment()
{
    int flow=INF;
    for(int x(t);x!=s;x=edges[p[x]].u)
        flow=MIN(flow,edges[p[x]].cap);
    for(int x(t);x!=s;x=edges[p[x]].u)
        edges[p[x]].cap-=flow,edges[p[x]^1].cap+=flow;
    return flow;
}
inline int isap()
{
    int x(s),res(0);
    bfs();
    memcpy(cur,point,num*sizeof(int));
    while(d[s]<num)
    {
        if(x==t)res+=augment(),x=s;
        bool flag=0;
        for(int i=cur[x];i!=-1;i=edges[i].next)
            if(edges[i].cap&&d[x]-1==d[edges[i].v])
            {
                cur[x]=i;
                flag=1;
                x=edges[i].v;
                p[x]=i;
                break;
            }
        if(!flag)
        {
            int delta=num;
            for(int i=point[x];i!=-1;i=edges[i].next)
                if(edges[i].cap&&d[edges[i].v]<delta)
                    delta=d[edges[i].v],cur[x]=i;
            if(!(--gap[d[x]]))break;
            gap[d[x]=delta+1]++;
            if(x!=s)x=edges[p[x]].u;
        }
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    s=0;t=(n<<1^1)+1;num=t+1;
    memset(point,0xff,sizeof(point));
    for(int i=1;i<=n;i++)
        {
            scanf("%d",f+i);
            sum+=f[i];
            addedge(s,i<<1,f[i]);
            addedge(i<<1^1,t,f[i]);
        }
    for(int i=1,u,v,w;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            addedge(u<<1,v<<1^1,w);
        }
    printf("%d\n",sum-isap());
    return 0;
}

Comments

comments powered by Disqus