BZOJ3442:学习小组 费用流
思路:
一开始YY了一个上下界最小费用流,结果有负圈...看来只有消圈姿势对才能搞了.
其实只有一个问题就是如何用最大流来限制参加的人数尽可能多,我们可以连接:
S−>i Maxcap=k Cost=0
i−>T Maxcap=k−1 Cost=0
这样就确保了最大流中每个人必定会走1的流量.
剩下的就水了.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include<cstdio>#include<cstring>#include<cctype>#include<climits>#include<algorithm>#include<queue>using namespace std; #define INF 0x3f3f3f3f int cnt;struct CostFlowSolver{ int head[210],next[2000010],end[2000010],flow[2000010],cost[2000010],ind; int d[210],ld[210],lb[210];bool inq[210];queue<int>q; inline void reset(){ind=0,memset(head,-1,sizeof head);} inline void addedge(int a,int b,int f,int c){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f,cost[q]=c;} inline void make(int a,int b,int f,int c){addedge(a,b,f,c),addedge(b,a,0,-c);} inline bool spfa(int S,int T){ memset(d,0x3f,sizeof d),d[S]=0,inq[S]=1,q.push(S); while(!q.empty()){ int i=q.front();q.pop(),inq[i]=0;for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]>d[i]+cost[j]){ d[end[j]]=d[i]+cost[j],ld[end[j]]=i,lb[end[j]]=j;if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]); } }return d[T]!=INF; } inline int Mincost(int S,int T){ int res=0,Min,i; while(spfa(S,T)){for(Min=INF,i=T;i^S;i=ld[i])Min=min(Min,flow[lb[i]]);for(i=T;i^S;i=ld[i])flow[lb[i]]-=Min,flow[lb[i]^1]+=Min;res+=Min*d[T];} return res; }}SteinsGate; int c[110],f[110];int main(){ int n,m,k;scanf("%d%d%d",&n,&m,&k);register int i,j; for(i=1;i<=m;++i)scanf("%d",&c[i]);for(i=1;i<=m;++i)scanf("%d",&f[i]); cnt=n+m;int S=0,T=++cnt; SteinsGate.reset(); for(i=1;i<=n;++i)SteinsGate.make(S,i,k,0); for(i=1;i<=n;++i)if(k>1)SteinsGate.make(i,T,k-1,0); int x;for(i=1;i<=n;++i)for(j=1;j<=m;++j){scanf("%1d",&x);if(x)SteinsGate.make(i,n+j,1,-f[j]);} for(j=1;j<=m;++j)for(i=1;i<=n;++i)SteinsGate.make(n+j,T,1,c[j]*(2*i-1)); printf("%d",SteinsGate.Mincost(S,T)); return 0;} |
评论 (0)