poj 2987 Firing 最大權閉合圖 網絡流

最大權閉合的求法參看黑書

[cpp]
#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std; 
const int maxn=5e3+9,maxm=6e4+9; 
const long long inf=(long long)1<<50; 
int level[maxn],head[maxn],que[maxn]; 
int lon; 
struct 
{ 
    int next,to; 
    long long w; 
}e[maxm*10]; 
 
 
void edgeini() 
{ 
    memset(head,-1,sizeof(head)); 
    lon=-1; 
} 
 
 
void edgemake(int from,int to,long long w) 
{ 
    e[++lon].to=to; 
    e[lon].w=w; 
    e[lon].next=head[from]; 
    head[from]=lon; 
} 
 
 
int makelevel(int s,int t) 
{ 
    memset(level,0,sizeof(level)); 
    level[s]=1; 
    int top=0; 
    que[++top]=s; 
    for(int i=1;i<=top;i++) 
    { 
        int u=que[i]; 
        if(u==t) return(1); 
        for(int k=head[u];k!=-1;k=e[k].next) 
        if(!level[e[k].to]&&e[k].w) 
        { 
            que[++top]=e[k].to; 
            level[e[k].to]=level[u]+1; 
        } 
    } 
    return(0); 
} 
 
 
 
 
long long dfs(int now,long long maxf,int t) 
{ 
    if(now==t) return(maxf); 
    long long ret=0; 
    for(int k=head[now];k!=-1;k=e[k].next) 
    { 
        if(e[k].w&&level[e[k].to]==level[now]+1) 
        { 
            long long f=dfs(e[k].to,min(maxf-ret,e[k].w),t); 
            e[k].w-=f; 
            e[k^1].w+=f; 
            ret+=f; 
            if(ret==maxf) return(ret); 
        } 
    } 
    return(ret); 
} 
 
 
long long dinic(int s,int t) 
{ 
    long long ans=0; 
    while(makelevel(s,t)) ans+=dfs(s,inf,t); 
 
 
    return(ans); 
} 
 
 
int flag[maxn]; 
int dfs(int t) 
{ 
    int ret=1; 
    flag[t]=1; 
    for(int k=head[t];k!=-1;k=e[k].next) 
    if(e[k].w>0) 
    { 
        int u=e[k].to; 
        if(!flag[u]) 
        ret+=dfs(u); 
    } 
    return(ret); 
} 
 
 
int main() 
{ 
    int n,m; 
    while(scanf("%d %d",&n,&m)!=EOF) 
    { 
        edgeini(); 
        long long sum=0; 
        for(int i=1,tmp;i<=n;i++) 
        { 
            scanf("%d",&tmp); 
            if(tmp>0) 
            { 
                sum+=tmp; 
                edgemake(0,i,tmp); 
                edgemake(i,0,0); 
            } 
            else 
            { 
                edgemake(i,n+1,-tmp); 
                edgemake(n+1,i,0); 
            } 
        } 
        for(int i=1,from,to;i<=m;i++) 
        { 
            scanf("%d %d",&from,&to); 
            edgemake(from,to,inf); 
            edgemake(to,from,0); 
        } 
 
 
        memset(flag,0,sizeof(flag)); 
        long long ans=dinic(0,n+1); 
        printf("%d ",dfs(0)-1); 
 
 
        printf("%lld\n",sum-ans); 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=5e3+9,maxm=6e4+9;
const long long inf=(long long)1<<50;
int level[maxn],head[maxn],que[maxn];
int lon;
struct
{
    int next,to;
    long long w;
}e[maxm*10];

void edgeini()
{
    memset(head,-1,sizeof(head));
    lon=-1;
}

void edgemake(int from,int to,long long w)
{
    e[++lon].to=to;
    e[lon].w=w;
    e[lon].next=head[from];
    head[from]=lon;
}

int makelevel(int s,int t)
{
    memset(level,0,sizeof(level));
    level[s]=1;
    int top=0;
    que[++top]=s;
    for(int i=1;i<=top;i++)
    {
        int u=que[i];
        if(u==t) return(1);
        for(int k=head[u];k!=-1;k=e[k].next)
        if(!level[e[k].to]&&e[k].w)
        {
            que[++top]=e[k].to;
            level[e[k].to]=level[u]+1;
        }
    }
    return(0);
}

long long dfs(int now,long long maxf,int t)
{
    if(now==t) return(maxf);
    long long ret=0;
    for(int k=head[now];k!=-1;k=e[k].next)
    {
        if(e[k].w&&level[e[k].to]==level[now]+1)
        {
            long long f=dfs(e[k].to,min(maxf-ret,e[k].w),t);
            e[k].w-=f;
            e[k^1].w+=f;
            ret+=f;
            if(ret==maxf) return(ret);
        }
    }
    return(ret);
}

long long dinic(int s,int t)
{
    long long ans=0;
    while(makelevel(s,t)) ans+=dfs(s,inf,t);

    return(ans);
}

int flag[maxn];
int dfs(int t)
{
    int ret=1;
    flag[t]=1;
    for(int k=head[t];k!=-1;k=e[k].next)
    if(e[k].w>0)
    {
        int u=e[k].to;
        if(!flag[u])
        ret+=dfs(u);
    }
    return(ret);
}

int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        edgeini();
        long long sum=0;
        for(int i=1,tmp;i<=n;i++)
        {
            scanf("%d",&tmp);
            if(tmp>0)
            {
                sum+=tmp;
                edgemake(0,i,tmp);
                edgemake(i,0,0);
            }
            else
            {
                edgemake(i,n+1,-tmp);
                edgemake(n+1,i,0);
            }
        }
        for(int i=1,from,to;i<=m;i++)
        {
            scanf("%d %d",&from,&to);
            edgemake(from,to,inf);
            edgemake(to,from,0);
        }

        memset(flag,0,sizeof(flag));
        long long ans=dinic(0,n+1);
        printf("%d ",dfs(0)-1);

        printf("%lld\n",sum-ans);
    }
    return 0;
}