CodeVS 1028 花店橱窗布置 【费用流】
注意要求最大值,所以边权取反,最后答案取反即可。
$O(???)$(我不会估算费用流的复杂度……反正可过)
# include <stdio.h> # include <string.h> # include <queue> # include <algorithm> using namespace std; int F,V; int a[101][101]; const int Max=80010; int tot=1,head[Max],next[Max],to[Max],flow[Max],w[Max],S,T; inline void add(int u,int v,int fl,int wx) { tot++;next[tot]=head[u];head[u]=tot;to[tot]=v;flow[tot]=fl,w[tot]=wx; tot++;next[tot]=head[v];head[v]=tot;to[tot]=u;flow[tot]=0,w[tot]=-wx; } queue<int> q; bool vis[Max]; int d[Max],ans; int pre[Max]; inline bool spfa() { memset(vis,0,sizeof(vis)); while(!q.empty()) q.pop(); memset(d,10300023,sizeof(d)); vis[S]=1,q.push(S),d[S]=0; while(!q.empty()) { int top=q.front();q.pop(); vis[top]=0; for (int i=head[top];i;i=next[i]) { if(d[top]+w[i]<d[to[i]]&&flow[i]) { d[to[i]]=d[top]+w[i]; pre[to[i]]=i; if(!vis[to[i]]) { vis[to[i]]=1; q.push(to[i]); } } } } if(d[T]>=10300023) return false; return true; } inline void mincost() { int xm=1e9; for (int i=pre[T];i;i=pre[to[i^1]]) xm=min(xm,flow[i]); for (int i=pre[T];i;i=pre[to[i^1]]) { flow[i]-=xm; flow[i^1]+=xm; ans+=xm*w[i]; } } int main() { scanf("%d%d",&F,&V); for (int i=1;i<=F;++i) for (int j=1;j<=V;++j) scanf("%d",&a[i][j]); S=0,T=F+V+2; for (int i=1;i<=F;++i) { add(S,i,1,0); for (int j=1;j<=V;++j) add(i,j+F,1,-a[i][j]); } for (int i=1;i<=V;++i) add(i+F,T,1,0); while(spfa()) mincost(); printf("%d\n",-ans); return 0; }
2023年4月16日 22:09
Bangladesh Education Board DPE has conducted the class 8th grade Junior School Certificate Exam and Junior Dakhil Certificate Exam from 1st to 15th November at all centers division-wise under Ministry of Primary and Mass Education (MOPME), bdjscresult2018.com and the class 8th grade terminal examination tests are successfully conducted for all eligible JSC/JDC students for the academic year The students who have qualified in this JSC/JDC exams they will get a stipend from the government of Bangladesh to continue their higher class easily and this very helpful to every student.