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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
|
using namespace std;
typedef long long ll; int n,m; const int maxn = 3000; const ll INF = 1e18;
struct { int from,to; ll cap,flow; };
struct Dinic{ int n,m,s,t; vector<edge> edges; vector<int> G[maxn]; bool vis[maxn]; ll d[maxn]; int cur[maxn];
void init(int n){ this->n = n; edges.clear(); for(int i=0;i<=n;i++)G[i].clear(); }
void addedge(int from,int to,ll cap){ edges.push_back(edge{from,to,cap,0}); edges.push_back(edge{to,from,0,0}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); }
bool bfs(){ memset(vis,0,sizeof(vis)); queue<int> q; q.push(s); d[s] = 0; vis[s] = 1; while(!q.empty()){ int x = q.front(); q.pop(); for(int i=0;i<G[x].size();i++){ edge &e = edges[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow){ vis[e.to] = 1; d[e.to] = d[x] + 1; q.push(e.to); } } } return vis[t]; } ll dfs(int x,ll a){ if(x==t||a==0)return a; ll flow = 0,f; for(int &i = cur[x];i<G[x].size();i++){ edge &e = edges[G[x][i]]; if(d[x] + 1 == d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){ e.flow+=f; edges[G[x][i]^1].flow -=f; flow+=f; a-=f; if(a==0)break; } } return flow; }
ll maxflow(int s,int t){ this->s = s; this->t = t; ll flow = 0; while(bfs()){ memset(cur,0,sizeof(cur)); flow+=dfs(s,INF); } return flow; } }solver;
int main(){ ios::sync_with_stdio(false); cin>>n>>m; solver.init(n+m+2); int s = 0,t = n+m+1; ll sum = 0; for(int i=1;i<=n;i++){ ll a; cin>>a; solver.addedge(m+i,t,a); } for(int i=1;i<=m;i++){ int a,b; ll c; cin>>a>>b>>c; sum+=c; solver.addedge(s,i,c); solver.addedge(i,m+a,INF); solver.addedge(i,m+b,INF); } ll res = solver.maxflow(s,t); cout<<sum-res<<endl; return 0; }
|
近期评论