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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
| #include<cstdio> #include<cstring> using namespace std; const int inf=1e9; const int N=3e6; struct edge { int from,to,next,cap,flow; }e[N]; int cnt,n,m,r,sour,sink,head[N],l[N],ans,q[N],p[N],tot; inline int min(int i,int j) { return i<j?i:j; } int dfs(int x,int now) { if(x==sink||!now) return now; int t=now,detla; for(int i=head[x];i;i=e[i].next) { if(e[i].cap>e[i].flow&&l[e[i].to]==l[x]+1) { detla=dfs(e[i].to,min(t,e[i].cap-e[i].flow)); if(!detla) l[e[i].to]=0; e[i].flow+=detla; e[((i-1)^1)+1].flow-=detla; t-=detla; if(t==0) break; } } return now-t; } inline void add(int u,int v,int l) { e[++cnt]=(edge){u,v,head[u],l,0}; head[u]=cnt; e[++cnt]=(edge){v,u,head[v],0,0}; head[v]=cnt; } inline bool find() { memset(l,0,sizeof(l)); int h=1,t=1; q[1]=sour; l[sour]=1; while(h<=t) { int x=q[h++]; for(int i=head[x];i;i=e[i].next) if(!l[e[i].to]&&e[i].cap>e[i].flow) { q[++t]=e[i].to; l[e[i].to]=l[x]+1; if(e[i].to==sink) return true; } } return false; } inline void dinic() { while(find()) ans+=dfs(sour,inf); } inline void read(int &x) { char ch; int f=1; x=0; do { if(ch=='-') f=-1; ch=getchar(); }while(!('0'<=ch&&ch<='9')); do { x=(x<<3)+(x<<1)+ch-48; ch=getchar(); }while('0'<=ch&&ch<='9'); x*=f; } int main() { int _; read(_); ++_; while(--_) { cnt=0; ans=0; tot=0; memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); read(n); read(m); sour=0; sink=n+m+1; for(int i=1;i<=n;i++) { int r; read(r); add(i+m,sink,r); } for(int i=1;i<=m;i++) { int a,b,c; read(a); read(b); read(c); add(i,a+m,inf); add(i,b+m,inf); add(sour,i,c); tot+=c; } dinic(); printf("%d\n",tot-ans); } return 0; }
|