@OceanEye7年前
04/28
23:34
最小割
从源点向每个人连收益大小的边
人向站连大小为INF的边
站向汇连大小为成本的边
这个时候的割有三种情况：
1.把收益割掉了，此时支出>收入
2.把支出割掉了，此时支出<收入
3.支出和收入同时割掉了，支出=收入
总的答案就是sum-割
|
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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cstdlib> #include <iostream> #include <queue> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; #define E 400000 #define N 70050 struct Tedge { int from,to,cap,flow; }edge[E]; #define FROM edge[i].from #define TO edge[i].to #define FLO (edge[i].cap-edge[i].flow) int e_tot,fst[N],NXT[E]; int n,m,tot; void add_e(int _,int __,int ___) { edge[e_tot].from=_; edge[e_tot].to=__; edge[e_tot].cap=___; edge[e_tot].flow=0; NXT[e_tot]=fst[_]; fst[_]=e_tot++; edge[e_tot].from=__; edge[e_tot].to=_; edge[e_tot].cap=___; edge[e_tot].flow=___; NXT[e_tot]=fst[__]; fst[__]=e_tot++; } #define calc(x) (x+m) #define S 0 #define T N-1 void pre() { memset(fst,-1,sizeof(fst)); read(n); read(m); int _,__,___; for(int i=1;i<=n;i++) { read(_); add_e(calc(i),T,_); } for(int i=1;i<=m;i++) { read(_); read(__); read(___); add_e(S,i,___); tot+=___; add_e(i,calc(__),INF); add_e(i,calc(_),INF); } } int dist[N],p[N],cur[N],cnt[N]; int Augment() { int node,cur,i; cur=INF; node=T; while(node!=S) { i=p[node]; cur=min(cur,FLO); node=FROM; } node=T; while(node!=S) { i=p[node]; edge[i].flow+=cur; edge[i^1].flow-=cur; node=FROM; } return cur; } bool bfs() { int x; dist[T]=1; queue<int> Q; Q.push(T); while(!Q.empty()) { x=Q.front(); Q.pop(); for(int i=fst[x];~i;i=NXT[i]) if(!FLO&&!dist[TO]) { Q.push(TO); dist[TO]=dist[x]+1; } } return dist[S]!=0; } int ISAP() { int node=S,ret=0; bool flag; if(!bfs()) return false; for(int i=0;i<N;i++) { cur[i]=fst[i]; if(dist[i]) cnt[dist[i]]++; } while(dist[S]<=n*2+2) { if(node==T) { ret+=Augment(); node=S; } flag=false; for(int i=cur[node];~i;i=NXT[i]) if(dist[TO]==dist[node]-1&&FLO) { p[TO]=cur[node]=i; node=TO; flag=true; break; } if(flag) continue; int M=N-1; cur[node]=fst[node]; for(int i=fst[node];~i;i=NXT[i]) { if(!FLO) continue; M=min(M,dist[TO]+1); } if(!--cnt[dist[node]]) break; cnt[dist[node]=M]++; if(node!=S) node=edge[p[node]].from; } return ret; } int main() { pre(); printf("%d\n",tot-ISAP()); return 0; } |