网络流/最大权闭合图
题目:http://codeforces.com/problemset/problem/311/E
嗯这是最大权闭合图中很棒的一道题了~
能够1A真是开心~也是我A掉的第一道E题吧……(其实是这题放在E偏水了吧……)
题目大意:有n个0/1变量,给定每个变量的初值,以及每个变量取反的费用$v_i$,有m组需求,对于第 i 组需求,如果集合$S_i$里面的每个变量的值都为给定的v(0 or 1),则获得$\omega_i$的利润,求最大总利润。(其中某些请求若是无法满足还需额外付出g的代价)
这题其实用的思路有点类似最小割……假定跟S相连的变量是选1,跟T相连的是选0,那么对于初值为1的点连i->T,容量为$v_i$,初值为0的连S->i,容量为$v_i$,表示将这些变量取反的代价。
然后考虑需求,如果是要求全为1,则对每个$S_i$中的元素$i$连边 i->n+j ,费用为INF,同时连n+j->T,容量为$\omega_i$;如果是全为0的请求则反过来。
另外这题有个特殊的要求:一些无法满足的请求需要额外付出g的代价。其实这很好解决,我们的答案是$\sum \omega_i-max_flow$,那么我们对于“朋友的请求”,就在tot+了$\omega_i$后,建边时改成容量为$\omega_i+g$即可。
# | When | Who | Problem | Lang | Verdict | Time | Memory |
---|---|---|---|---|---|---|---|
10516710 | 2015-03-29 17:21:31 | Tunix | E - Biologist | GNU C++ | Accepted | 92 ms | 28188 KB |
//CF 311E
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
using namespace std;
inline int getint(){
int v=,sign=; char ch=getchar();
while(ch<''||ch>''){ if (ch=='-') sign=-; ch=getchar();}
while(ch>=''&&ch<=''){ v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=1e6+,M=,INF=~0u>>;
typedef long long LL;
/******************tamplate*********************/
int n,m,g,tot,ans;
int a[N],v[N];
struct edge{int to,v;};
struct Net{
edge E[M];
int head[N],next[M],cnt;
void ins(int x,int y,int v){
E[++cnt]=(edge){y,v};
next[cnt]=head[x]; head[x]=cnt;
}
void add(int x,int y,int v){
ins(x,y,v); ins(y,x,);
}
int S,T,cur[N],d[N],Q[N];
bool mklevel(){
memset(d,-,sizeof d);
d[S]=;
int l=,r=-;
Q[++r]=S;
while(l<=r){
int x=Q[l++];
for(int i=head[x];i;i=next[i])
if (d[E[i].to]==- && E[i].v){
d[E[i].to]=d[x]+;
Q[++r]=E[i].to;
}
}
return d[T]!=-;
}
int dfs(int x,int a){
if (x==T) return a;
int flow=;
for(int &i=cur[x];i && flow<a;i=next[i])
if (E[i].v && d[E[i].to]==d[x]+){
int f=dfs(E[i].to,min(a-flow,E[i].v));
E[i].v-=f;
E[i^].v+=f;
flow+=f;
}
if (!flow) d[x]=-;
return flow;
}
void Dinic(){
while(mklevel()){
F(i,S,T) cur[i]=head[i];
ans+=dfs(S,INF);
}
}
void init(){
n=getint(); m=getint(); g=getint();
F(i,,n) a[i]=getint();
F(i,,n) v[i]=getint();
cnt=; S=; T=n+m+; ans=tot=;
F(i,,n) if(a[i]) add(S,i,v[i]);else add(i,T,v[i]);
F(i,,m){
int x=getint(), w=getint(), k=getint(); tot+=w;
F(j,,k){
int y=getint();
if (!x) add(y,n+i,INF);
else add(n+i,y,INF);
}
int y=getint();
if(y) w+=g;//if friend
if (!x) add(n+i,T,w);
else add(S,n+i,w);
}
}
}G1; int main(){
#ifndef ONLINE_JUDGE
freopen("311E.in","r",stdin);
freopen("311E.out","w",stdout);
#endif
G1.init(); G1.Dinic();
printf("%d\n",tot-ans);
return ;
}