Wa 1 TLE 8~11 Dinic 求调
查看原帖
Wa 1 TLE 8~11 Dinic 求调
941431
Autream楼主2024/7/2 20:01
// Problem: P3381 【模板】最小费用最大流
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3381
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Author: Li_Feiy
#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)a[i]=read()
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
int read() {
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
CI N=1e5+5,INF=0x3f3f3f3f3f3f3f3f;
int n,m,s,t,cst,tot=1,vis[N],dis[N],now[N],head[N];
struct edge {
	int to,nex,flow,data;
}e[N<<1];
void add(int x,int y,int f,int z) {
	e[++tot].to=y;
	e[tot].flow=f;
	e[tot].data=z;
	e[tot].nex=head[x];
	head[x]=tot;
}
bool spfa() {
	std::queue<int> q;
	mem(dis,0x3f);
	memcpy(now,head,sizeof now);
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	while(!q.empty()) {
		int x=q.front();
		q.pop();
		vis[x]=0;
		erg(i,x) {
			int y=e[i].to,z=e[i].data;
			if(e[i].flow<=0) continue;
			if(dis[y]>dis[x]+z) {
				dis[y]=dis[x]+z;
				if(!vis[y]) {
					q.push(y);
					vis[y]=1;
				}
			}
		}
	}
	return dis[t]!=INF;
}
int dfs(int x,int flow) {
	if(x==t) return flow;
	vis[x]=1;
	int tmp=flow;
	for(int i=now[x];i&&tmp;i=e[i].nex) {
		int y=e[i].to,z=e[i].data;
		if(!e[i].flow||dis[y]!=dis[x]+z||vis[y]) continue;
		int k=dfs(y,std::min(tmp,z));
		cst+=k*z;
		e[i].flow-=k;
		e[i^1].flow+=k;
		tmp-=k;
	}
	vis[x]=0;
	return flow-tmp;
}
int mcmf() {
	int ans=0;
	while(spfa()) {
		ans+=dfs(s,INF);
	}
	return ans;
}
signed main() {
	n=read(),m=read(),s=read(),t=read();
	rep(i,1,m) {
		int x=read(),y=read(),f=read(),z=read();
		add(x,y,f,z);
		add(y,x,0,-z);
	}
	std::cout<<mcmf()<<" "<<cst;
    return 0;
}
2024/7/2 20:01
加载中...