社区讨论
为啥WA了一个qwq?
P4015运输问题参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @mi7riain
- 此快照首次捕获于
- 2025/11/21 02:25 4 个月前
- 此快照最后确认于
- 2025/11/21 02:25 4 个月前
RT,WA了#6
CPP#include<bits/stdc++.h>
using namespace std;
const int MAXN=210;
const int MAXM=5e4+10;
const int INF=0x3f3f3f3f;
int n,m,cnt,s,t,cost;
int head[MAXN],cur[MAXN],dis[MAXN][2],vis[MAXN],work[MAXN];
int nxt[MAXM],to[MAXM],w[MAXM][2],c[MAXM][2];
int Read(){
int i=0,f=1;
char c;
for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());
if(c=='-')
f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())
i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
void Add(int x,int y,int z,int f){
nxt[cnt]=head[x];
head[x]=cnt;
to[cnt]=y;
w[cnt][0]=w[cnt][1]=z;
c[cnt][0]=f;
c[cnt][1]=-f;
cnt++;
}
void add(int x,int y,int z,int f){
Add(x,y,z,f);
Add(y,x,0,-f);
}
int SPFA(int type){
memset(dis,INF,sizeof(dis));
memset(work,0,sizeof(work));
dis[s][type]=0;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u];i!=-1;i=nxt[i]){
int v=to[i];
if(dis[v][type]>dis[u][type]+c[i][type]&&w[i][type]){
dis[v][type]=dis[u][type]+c[i][type];
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return dis[t][type]<INF;
}
int dfs(int u,int flow,int type){
if(u==t){
cost+=flow*dis[u][type];
return flow;
}
work[u]=1;
int ret=0;
for(int &i=cur[u];i!=-1;i=nxt[i]){
int v=to[i];
if(dis[v][type]==dis[u][type]+c[i][type]&&w[i][type]&&!work[v]){
int di=dfs(v,min(w[i][type],flow),type);
if(di){
w[i][type]-=di;
w[i^1][type]+=di;
ret+=di;
if(ret==flow)
break;
}
}
}
return ret;
}
int dinic(int type){
int ret=0;
while(SPFA(type)){
for(int i=s;i<=t;++i)
cur[i]=head[i];
ret+=dfs(s,INF,type);
}
return ret;
}
int main(){
memset(head,-1,sizeof(head));
n=Read(),m=Read();
s=0,t=n+m+1;
for(int i=1;i<=n;++i){
int x=Read();
add(s,i,x,0);
}
for(int i=1;i<=m;++i){
int x=Read();
add(i+n,t,x,0);
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
int x=Read();
add(i,j+n,INF,x);
}
}
dinic(0);
cout<<cost<<endl;
cost=0;
dinic(1);
cout<<-cost;
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...