网络流算法

#include<cstdio> #include<algorithm rel='nofollow' onclick='return false;'> #include<cstring> #include<iostream> #include<map> #include<set> #include<bitset> #include<vector> #include<cmath> #define N 505 #define M 1000005 #define K 18 #define ls (t<<1) #define rs ((t<<1)|1) #define mid ((l+r)>>1) #define fi first #define se second #define pb push_back #define Mo 1000000007 using namespace std; int read() { int x,f=0; char c; while (c=getchar(),c<'0'||c>'9'); if (c=='-') f=1,c=getchar(); x=c-'0'; while (c=getchar(),c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0'; return f?-x:x; } struct Node{ int flow,ed,before; }s[M]; int i,j,m,n,p,k,k1,fox[N*3],S; struct Bian{ int x,y,z; }B[M]; int a[N],b[N],st,ed; void add(int x,int y,int flow) { s[++k1].ed=y; s[k1].before=fox[x]; fox[x]=k1; s[k1].flow=flow; s[++k1].ed=x; s[k1].before=fox[y]; fox[y]=k1; s[k1].flow=0; } const int inf=(int)1e9; int dis[N*3],Q[N*3],fa[N*3]; int bfs(int x) { int i,l; Q[Q[0]=1]=x; memset(dis,-1,sizeof(dis)); dis[st]=0; for (l=1;l<=Q[0]&&dis[ed]==-1;++l) { int p=Q[l]; for (i=fox[p];i;i=s[i].before) if (s[i].flow) { int k=s[i].ed; if (dis[k]==-1) dis[k]=dis[p]+1,Q[++Q[0]]=k,fa[k]=i; } } return dis[ed]!=-1; } int dfs(int x,int flow) { int i,a,nowans=0; if (x==ed) return flow; for (i=fox[x];i&&flow;i=s[i].before) if (s[i].flow) { int p=s[i].ed; if (dis[p]==dis[x]+1) { a=dfs(p,min(flow,s[i].flow)); s[i].flow-=a; s[i^1].flow+=a; flow-=a; nowans+=a; } } if (!nowans) dis[x]=-1; return nowans; } int maxflow() { int i,ans=0; while (bfs(st)) ans+=dfs(st,inf); return ans; } int cmp(Bian a,Bian b) { if (a.x!=b.x) return a.x<b.x; return a.y<b.y; } void Main() { k1=1; memset(fox,0,sizeof(fox)); scanf("%d%d%d",&n,&m,&S); for (i=1;i<=m;++i) B[i].x=read(),B[i].y=read(),B[i].z=read(); for (i=1;i<=n;++i) a[i]=read(); for (i=1;i<=n;++i) b[i]=read(); st=3*n+1; ed=st+1; for (i=1;i<=n;++i) { add(i,i+n,b[i]); add(i+n,i+2*n,a[i]); add(i+2*n,ed,inf); } // sort(B+1,B+m+1,cmp); for (i=1;i<=m;i++) add(B[i].y+n,B[i].x,B[i].z); add(st,S,inf); printf("%d\n",maxflow()); } int main() { // freopen("1.in","r",stdin); int T; scanf("%d",&T); for (;T--;) Main(); } /* 1 5 5 5 1 2 5 1 3 5 2 4 8 4 5 10 3 5 15 100 100 100 200 200 3 5 7 9 1000000 */