CF 331 E. Biologist
CF 331 E. Biologist题目描述 题目大意:有(n)个点,初始时每个点为黑色或者白色,你可以花费(v_i)的代价将一个点反色。然后你有许多计划,每个计划要求一个点集中的所有点为同种颜色。满足了一个计划就可以得到(w_i)相应的价值,某些计划如果没有被满足,还会付出(g)的代价。 感觉这个题有点最大权闭合子图的样子,(g)的额外代价也很鸡肋。 然后我们考虑这道题的反色操作。如果第(i)个点本来是白色的,那么我们连((S,i,v_i)),否则连((i,T,v_i))。如果将这种边割了,就代表将这个点反色。 然后对于第(i)个计划,如果他要求的点集为白色,但是点集中的点(x)为黑色,则我们连((i+n,x,infty));反之连((x,i+n,infty))。然后对于白色计划连((S,w_i+[i==friend]*g));对于黑色计划连((i+n,w_i+[i==friend]*g))。 如果(Sto T)有路径就代表有冲突了。 然后如果有不同颜色的计划的点集中有交,那么他们不可能同时选,于是连他们之间连一条(infty)的边。然后我们可以优化一下这些边。 假设一个白色计划,它的点集中有白色点,那么我们也连((i+n,infty)),黑色计划同理。 代码: #include<bits/stdc++.h> #define ll long long #define N 15005 using namespace std; inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;} int n,m,g; int col[N]; int v[N],fri[N],w[N]; int sex[N]; struct road { int to,next; int flow; }s[N<<3]; int h[N],cnt=1; int cur[N]; void add(int i,int j,int f) { s[++cnt]=(road) {j,h[i],f};h[i]=cnt; s[++cnt]=(road) {i,h[j],0};h[j]=cnt; } int S,T; int dis[N]; queue<int>q; bool bfs() { memset(dis,0x3f,sizeof(dis)); q.push(S); dis[S]=0; while(!q.empty()) { int v=q.front(); q.pop(); for(int i=h[v];i;i=s[i].next) { int to=s[i].to; if(s[i].flow&&dis[to]>dis[v]+1) { dis[to]=dis[v]+1; q.push(to); } } } return dis[T]<1e9; } int dfs(int v,int maxf) { if(v==T) return maxf; int ret=0; for(int &i=cur[v];i;i=s[i].next) { int to=s[i].to; if(s[i].flow&&dis[to]==dis[v]+1) { int dlt=dfs(to,min(maxf,s[i].flow)); s[i].flow-=dlt; s[i^1].flow+=dlt; ret+=dlt; maxf-=dlt; if(!maxf) return ret; } } return ret; } int dinic() { int ans=0; while(bfs()) { while(1) { memcpy(cur,h,sizeof(h)); int tem=dfs(S,1e9); if(!tem) break; ans+=tem; } } return ans; } int sum=0; int main() { n=Get(),m=Get(),g=Get(); T=n+m+1; for(int i=1;i<=n;i++) col[i]=Get(); for(int i=1;i<=n;i++) { v[i]=Get(); if(!col[i]) add(S,v[i]); else add(i,v[i]); } for(int i=1;i<=m;i++) { sex[i]=Get(),w[i]=Get(); sum+=w[i]; int k=Get(); while(k--) { int a=Get(); if(sex[i]) add(a,1e9); else add(i+n,a,1e9); } fri[i]=Get(); } for(int i=1;i<=m;i++) { if(sex[i]) add(i+n,w[i]+fri[i]*g); else add(S,w[i]+fri[i]*g); } cout<<sum-dinic(); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |