【BZOJ1497】【NOI2006】最大获益

今年论文集里面也有这道题哦。。

就是网络流24题T2的弱化版

随意切

// <1497.cpp> - 05/17/16 22:07:59
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=60000,MAXM=400010;
const int INF=1e9;
int bt=1,b[MAXN],cur[MAXN],next[MAXM],to[MAXM],val[MAXM];
int n,m;
inline void add(int x,int y,int v){
    next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=v;
    next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=0;
}
int dis[MAXN];
inline bool fc(){
    for(int i=1;i<=n+m+1;i++)dis[i]=0;
    dis[0]=1;
    queue <int> q;
    q.push(0);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=b[now];i;i=next[i])
            if(val[i]>0&&!dis[to[i]]){
                dis[to[i]]=dis[now]+1;
                q.push(to[i]);
            }
    }
    return dis[n+m+1];
}
int dfs(int x,int M){
    if(x==n+m+1)return M;
    int ans=0,now;
    for(int &i=cur[x];i;i=next[i]){
        if(dis[to[i]]==dis[x]+1&&val[i]>0)
            if(now=dfs(to[i],min(M-ans,val[i]))){
                val[i]-=now;
                val[i^1]+=now;
                ans+=now;
                if(ans==M)return ans;
            }
    }
    return ans;
}
int main(){
    n=gi(),m=gi();
    for(int i=1;i<=n;i++)add(m+i,m+n+1,gi());
    int tot=0;
    for(int i=1;i<=m;i++){
        int a=gi(),b=gi(),c=gi();
        tot+=c;
        add(0,i,c);
        add(i,m+a,INF);
        add(i,m+b,INF);
    }
    int now,ans=0;
    while(fc()){
        for(int i=0;i<=n+m+1;i++)cur[i]=b[i];
        while(now=dfs(0,INF))ans+=now;
    }
    printf("%d",tot-ans);
    return 0;
}

// <1497.cpp> - 05/17/16 22:07:59

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=60000,MAXM=400010;

const int INF=1e9;

int bt=1,b[MAXN],cur[MAXN],next[MAXM],to[MAXM],val[MAXM];

int n,m;

inline void add(int x,int y,int v){

next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=v;

next[++bt]=b[y];b[y]=bt;to[bt]=x;val[bt]=0;

}

int dis[MAXN];

inline bool fc(){

for(int i=1;i<=n+m+1;i++)dis[i]=0;

dis[0]=1;

queue <int> q;

q.push(0);

while(!q.empty()){

int now=q.front();q.pop();

for(int i=b[now];i;i=next[i])

if(val[i]>0&&!dis[to[i]]){

dis[to[i]]=dis[now]+1;

q.push(to[i]);

}

return dis[n+m+1];

}

int dfs(int x,int M){

if(x==n+m+1)return M;

int ans=0,now;

for(int &i=cur[x];i;i=next[i]){

if(dis[to[i]]==dis[x]+1&&val[i]>0)

if(now=dfs(to[i],min(M-ans,val[i]))){

val[i]-=now;

val[i^1]+=now;

ans+=now;

if(ans==M)return ans;

}

return ans;

}

int main(){

n=gi(),m=gi();

for(int i=1;i<=n;i++)add(m+i,m+n+1,gi());

int tot=0;

for(int i=1;i<=m;i++){

int a=gi(),b=gi(),c=gi();

tot+=c;

add(0,i,c);

add(i,m+a,INF);

add(i,m+b,INF);

}

int now,ans=0;

while(fc()){

for(int i=0;i<=n+m+1;i++)cur[i]=b[i];

while(now=dfs(0,INF))ans+=now;

}

printf("%d",tot-ans);

return 0;

}