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.