今年论文集里面也有这道题哦。。
就是网络流24题T2的弱化版
随意切
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
// <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; } |
说点什么