社区讨论

为啥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 条回复,欢迎继续交流。

正在加载回复...