- #include<bits/stdc++.h>
- #define N 120005
- #define M 400005
- #define INF 2100000000
- using namespace std;
- int n,m,T,ans,sum,S;
- int to[M],nxt[M],w[M],li[N];
- int cnt;
- int d[N];
- int q[N*2];
- void Build(int x,int y,int z){
- to[++cnt]=y;
- nxt[cnt]=li[x];
- li[x]=cnt;
- w[cnt]=z;
- to[++cnt]=x;
- nxt[cnt]=li[y];
- li[y]=cnt;
- w[cnt]=0;
- }
- bool bfs(){
- memset(d,0,sizeof(d));
- int h,t,x;
- h=1;t=1;
- q[1]=S;
- d[S]=1;
- while (h!=t+1){
- x=q[h];
- for (int i=li[x];i>=0;i=nxt[i])
- if (w[i]&&!d[to[i]]){
- d[to[i]]=d[x]+1;
- q[++t]=to[i];
- if (t==N)
- t=0;
- }
- if (++h==N)
- h=0;
- }
- if (d[T])
- return true;
- else
- return false;
- }
- int dfs(int x,int y){
- if (x==T||y==0)
- return y;
- int f,ret=0;
- for (int i=li[x];i>=0;i=nxt[i])
- if (d[to[i]]==d[x]+1){
- f=dfs(to[i],min(w[i],y));
- w[i]-=f;
- w[i^1]+=f;
- y-=f;
- ret+=f;
- if (y==0)
- break;
- }
- return ret;
- }
- int main(){
- scanf("%d%d",&n,&m);
- T=n+m+1;
- cnt=-1;
- for (int i=0;i<=T;i++)
- li[i]=-1;
- int x,y,z;
- for (int i=1;i<=n;i++){
- scanf("%d",&x);
- Build(0,i,x);
- }
- for(int i=1;i<=m;i++){
- scanf("%d%d%d",&x,&y,&z);
- Build(n+i,T,z);
- Build(x,n+i,INF);
- Build(y,n+i,INF);
- sum+=z;
- }
- while(bfs())
- ans+=dfs(S,INF);
- printf("%d",sum-ans);
- }
来源: http://www.bubuko.com/infodetail-2757226.html