社区讨论

求助,dinic只有70分,T了三个点,其他点都是0ms过

P3376【模板】网络最大流参与者 2已保存回复 1

讨论操作

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

当前回复
1 条
当前快照
1 份
快照标识符
@mi6nym8d
此快照首次捕获于
2025/11/20 07:58
4 个月前
此快照最后确认于
2025/11/20 07:58
4 个月前
查看原帖
我真的不是水帖,,,刚才那个代码成了一坨。。
CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int inf=99999999;
const int maxm=100086;
const int maxn=10086;
int next[maxm],head[maxn],to[maxm],w[maxm],n,m,cnt=-1,cur[maxn],dep[maxn],s,t,j,k,l;
inline int HongkongReporter(){
	int x=0;char c=getchar();
	while (!isdigit(c)){
		c=getchar();
	}
	while (isdigit(c)){
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}return x;
}
inline void add(int x,int y,int z){
	to[++cnt]=y;next[cnt]=head[x];head[x]=cnt;w[cnt]=z;
	to[++cnt]=x;next[cnt]=head[y];head[y]=cnt;w[cnt]=0;
}
bool bfs(){
	queue<int> q;
	memset(dep,0,sizeof(dep));
	q.push(s);dep[s]=1;
	while (!q.empty()){
		int u=q.front();q.pop();
		for (int i=head[u];i!=-1;i=next[i]){
			int v=to[i];
			if (w[i]>0&&dep[v]==0){
				dep[v]=dep[u]+1;
				q.push(v);
			}
		}
	}
	if (dep[t])return 1;
	else return 0;
}

inline int dfs(int x,int dist){
	if (x==t)return dist;
	for (int& i=cur[x];i!=-1;i=next[i]){
		int v=to[i];
		if (dep[x]+1==dep[v]&&w[i]!=0){
			int d=dfs(v,min(dist,w[i]));
			if (d){
				w[i]-=d;
				w[i^1]+=d;
				return d;
			}
		}
	}
	return 0;
}
int dinic(){
	int ans=0;
	while (bfs()){
		for (int i=1;i<=n;i++)cur[i]=head[i];
		while (int d=dfs(s,inf))ans+=d;
	}
	return ans;
}
int main(){
	n=HongkongReporter();m=HongkongReporter();s=HongkongReporter();t=HongkongReporter();
	memset(head,-1,sizeof(head));
	memset(next,-1,sizeof(next));
	for (int i=1;i<=m;i++){
		j=HongkongReporter();k=HongkongReporter();l=HongkongReporter();
		if (j==k)continue;
		add(j,k,l);
	}
	printf("%d",dinic());
	return 0;
}

回复

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

正在加载回复...