BZOJ 1927 最小费用流问题

From lydrainbowcat

//By SiriusRen
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 2222
#define M 999999
#define mem(x,k) memset(x,k,sizeof(x))
int n,m,a[N],xx,yy,zz,T,d[N],minn[N],vis[N],with[N];
int first[N],next[M],v[M],edge[M],cost[M],tot,ans;
void Add(int x,int y,int C,int E){
    edge[tot]=E,cost[tot]=C,v[tot]=y,next[tot]=first[x],first[x]=tot++;
}
void add(int x,int y,int C,int E){Add(x,y,C,E),Add(y,x,-C,0);}
bool tell(){
    mem(d,0x3f),mem(minn,0x3f),mem(vis,0),mem(with,0);
    queue<int>q;d[0]=0;q.push(0);
    while(!q.empty()){
        int t=q.front();q.pop();vis[t]=0;
        for(int i=first[t];~i;i=next[i])
            if(d[v[i]]>d[t]+cost[i]&&edge[i]){
                d[v[i]]=d[t]+cost[i],minn[v[i]]=min(minn[t],edge[i]),with[v[i]]=i;
                if(!vis[v[i]])vis[v[i]]=1,q.push(v[i]);
            }
    }return d[T]!=0x3f3f3f3f;
}
int zeng(){
    for(int i=T;i;i=v[with[i]^1])
        edge[with[i]]-=minn[T],edge[with[i]^1]+=minn[T];
    return d[T];
}
int main(){
    memset(first,-1,sizeof(first));
    scanf("%d%d",&n,&m);
    T=n*2+1;
    for(int i=1;i<=n;i++)
        scanf("%d",&xx),add(0,i+n,xx,1),add(i+n,T,0,1),add(0,i,0,1);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&xx,&yy,&zz),add(min(xx,yy),max(xx,yy)+n,zz,1);
    while(tell())ans+=zeng();
    printf("%d
",ans);
}