网络流64分
查看原帖
网络流64分
328443
Textbook_blasphemy楼主2021/5/16 16:37

code

#include<bits/stdc++.h>
using namespace std;
const long long inf=1<<29, N=3000010;
int head[N],d[N];
long long n, m, s, t, tot, max_flow;
queue<long long> q;
struct node{
	long long to;
	long long next;
	long long dis;
}edge[N];
void add(long long x,long long y,long long z) {
	edge[++tot].dis=y;
	edge[tot].to=z;
	edge[tot].next=head[x];
	head[x]=tot;
	edge[++tot].dis=x;
	edge[tot].to=0;
	edge[tot].next=head[y];
	head[y]=tot;
}
long long bfs(){
	memset(d,0,sizeof(d));
	while(q.size())q.pop();
	q.push(s); 
	d[s]=1;
	while(q.size()){
		long long x=q.front();
		q.pop();
		for(long long i=head[x];i;i=edge[i].next)
			if(edge[i].to&&!d[edge[i].dis]){
				q.push(edge[i].dis);
				d[edge[i].dis]=d[x]+1;
				if(edge[i].dis==t)return 1;
			}
	}
	return 0;
}
long long dinic(long long x,long long flow){ 
	if(x==t)return flow;
	long long rest=flow,k;
	for(long long i=head[x];i&&rest;i=edge[i].next)
		if(edge[i].to&&d[edge[i].dis]==d[x]+1){
			k=dinic(edge[i].dis,min(rest,edge[i].to));
			if(!k)d[edge[i].dis]=0;
			edge[i].to-=k;
			edge[i^1].to+=k;
			rest-=k;
		}
	return flow-rest;
}
int main(){
	//freopen("P3376_7.txt","r",stdin);
	scanf("%lld%lld",&n,&m);
	scanf("%lld%lld",&s,&t);
	tot=1;
	for(long long i=1;i<=m;i++){
		long long x,y,c;
		scanf("%lld%lld%lld",&x,&y,&c);
		add(x,y,c);
	}
	long long flow=0;
	while(bfs())
		while(flow=dinic(s,inf))max_flow+=flow;
	printf("%lld",max_flow);
}

我下载了第七个测试点,不加文件读入RE(return 3221225477 w(゚Д゚)w)了,加了文件读入AC了(和out文件结果一样)

求答疑

2021/5/16 16:37
加载中...