【GDOI2017模拟8.11】生物学家

继续补。

Description

有n头牛，每头牛的性别已知。让第i头牛变性的代价为vi。 有m个人，第i个人想要ki头牛的性别都是他自己选定的那个（雌性或雄性），如果这样你会获得wi的收益。如果不满足有些人的需求，他们会给你带来g的代价（g为常数）。 求最大收益。 n<=10000,m<=2000,0<=wi,g,vi<=10000,ki<=10

Solution

一眼最小割。 但是建模得仔细想想。 我们的收益=总收益-变性的代价-不满足的收益-不满足的代价。 总收益一定，那么我们就是要（变性的代价+不满足的收益+不满足的代价最少） 很显然的，从源点想每头公牛连容量为vi的边，从每头母牛向汇点连容量为vi的边。 割掉表示把它变性。 然后，如何保证满足一个人的要求？ 从源点向每个要求雄性的人连容量为(wi(+g))的边，g可以在这里一起算。 然后，这个人向所有他所要求的牛连容量为正无穷的边。 正无穷是不会被割掉的。所以，如果源点连向他的那条边没被割掉，这些牛都同属于S集。 要求雌性的人同理。 然后就可以跑网络流了，注意10000个点，打裸SAP的人好自为之。

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define rep(i,a) for(int i=last[a];i;i=next[i]) #define N 12005 #define M 64005 using namespace std; const int inf=0x7fffffff; int n,m,g,l,S,T,s[N],v[N],x,y,z,w,ans; int last[N],t[M],f[M],next[M],dis[N],d[N]; void add(int x,int y,int z) { t[++l]=y;f[l]=z;next[l]=last[x];last[x]=l; t[++l]=x;f[l]=0;next[l]=last[y];last[y]=l; } bool bfs() { memset(dis,0,sizeof(dis));dis[S]=1; int i=0,j=1;d[1]=S; while (i<j) rep(k,d[++i]) if (!dis[t[k]]&&f[k]) dis[t[k]]=dis[d[i]]+1,d[++j]=t[k]; return dis[T]; } int dinic(int x,int y) { if (x==T) return y; int now=0; rep(i,x) if (dis[t[i]]==dis[x]+1&&f[i]) { int k=dinic(t[i],min(y,f[i])); f[i]-=k;f[i^1]+=k; y-=k;now+=k;if (!y) break; } if (!now) dis[x]=-1; return now; } int main() { scanf("%d%d%d",&n,&m,&g);l=1;S=0;T=n+m+1; fo(i,1,n) scanf("%d",&s[i]); fo(i,1,n) scanf("%d",&v[i]); fo(i,1,n) if (!s[i]) add(S,i,v[i]); else add(i,T,v[i]); fo(i,1,m) { scanf("%d%d%d",&x,&w,&y);ans+=w; fo(j,1,y) { scanf("%d",&z); if (!x) add(i+n,z,inf); else add(z,i+n,inf); } scanf("%d",&z);if (z) w+=g; if (!x) add(S,i+n,w); else add(i+n,T,w); } while (bfs()) ans-=dinic(S,inf); printf("%d",ans); }