社区讨论

错一个样例,求调

P1344[USACO4.4] 追查坏牛奶 Pollutant Control参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m43hzicp
此快照首次捕获于
2024/11/30 09:32
去年
此快照最后确认于
2025/11/04 13:38
4 个月前
查看原帖
CPP
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int M=1005,N=35;
struct node{
	int v,c,ne;
}a[M<<1];
int n,m,idx=1,h[N],s[M],e[M],c[M],d[N],S,T,cur[N];
void add(int aa,int bb,int cc){
	a[++idx]={bb,cc,h[aa]};
	h[aa]=idx;
}
bool bfs(){
	memset(d,0,sizeof d);
	queue<int>q;
	q.push(S);d[S]=1;
	while(q.size()){
		int u=q.front();q.pop();
		for(int i=h[u];i;i=a[i].ne){
			int v=a[i].v;
			if(d[v]==0&&a[i].c){
				d[v]=d[u]+1;
				if(v==T) return true;
				q.push(v);
			}
		}
	}
	return false;
}
int dfs(int u,int mf){
	if(u==T) return mf;
	int sum=0;
	for(int i=cur[u];i;i=a[i].ne){
		cur[u]=i;
		int v=a[i].v;
		if(d[v]==d[u]+1&&a[i].c){
			int f=dfs(v,min(mf,a[i].c));
			a[i].c-=f;
			a[i^1].c+=f;
			sum+=f;
			mf-=f;
			if(mf==0) break;
		}
	}
	if(sum==0) d[u]=0;
	return sum;
}
int dinic(){
	int f=0;
	while(bfs()){
		memcpy(cur,h,sizeof h);
		f+=dfs(S,1e9);
	}
	return f;
}
int main(){
	scanf("%d%d",&n,&m);
	S=1,T=n;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&s[i],&e[i],&c[i]);
		add(s[i],e[i],c[i]);
		add(e[i],s[i],0);
	}
	printf("%d ",dinic());
	idx=1;
	memset(h,0,sizeof h);
	for(int i=1;i<=m;i++){
		add(s[i],e[i],1);
		add(e[i],s[i],0);
	}
	printf("%d",dinic());
	return 0;
} 

回复

0 条回复,欢迎继续交流。

正在加载回复...