只有一行，包括一个整数，表示最大收益
和文理分科很像，不想写了太水了
1A哈哈哈哈哈
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=3005,M=2e6+5,INF=1e9; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f; } int n,m,s,t,a[N],b[N]; struct edge{ int v,c,f,ne; }e[M<<1]; int cnt,h[N]; inline void ins(int u,int v,int c){ cnt++; e[cnt].v=v;e[cnt].c=c;e[cnt].f=0;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].c=0;e[cnt].f=0;e[cnt].ne=h[v];h[v]=cnt; } int cur[N],d[N],vis[N]; int q[N],head,tail; bool bfs(){ head=tail=1; memset(vis,0,sizeof(vis)); d[s]=1;vis[s]=1;q[tail++]=s; while(head!=tail){ int u=q[head++]; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(!vis[v]&&e[i].c>e[i].f){ vis[v]=1;d[v]=d[u]+1; q[tail++]=v; if(v==t) return true; } } } return false; } int dfs(int u,int a){ if(u==t||a==0) return a; int flow=0,f; for(int &i=cur[u];i;i=e[i].ne){ int v=e[i].v; if(d[v]==d[u]+1&&(f=dfs(v,min(e[i].c-e[i].f,a)))>0){ flow+=f; e[i].f+=f; e[((i-1)^1)+1].f-=f; a-=f; if(a==0) break; } } if(a) d[u]=-1; return flow; } int dinic(){ int flow=0; while(bfs()){ for(int i=s;i<=t;i++) cur[i]=h[i]; flow+=dfs(s,INF); } return flow; } int sum; int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<=n;i++) a[i]=read(),sum+=a[i]; for(int i=1;i<=n;i++) b[i]=read(),sum+=b[i]; m=read();s=0;t=n+m+m+1; for(int i=1;i<=n;i++) ins(s,i,a[i]),ins(i,t,b[i]); for(int i=1;i<=m;i++){ int k=read(),c1=read(),c2=read(),a; sum+=c1+c2; int p1=n+i,p2=n+m+i; ins(s,p1,c1);ins(p2,t,c2); for(int i=1;i<=k;i++){ a=read(); ins(p1,a,INF); ins(a,p2,INF); } } printf("%d",sum-dinic()); }
原文：http://www.cnblogs.com/candy99/p/6347804.html