原始对偶 TLE 63pts 求助
查看原帖
原始对偶 TLE 63pts 求助
638537
g1ove楼主2024/7/19 11:35

rt

#include<bits/stdc++.h>
#define ll long long
#define N 50005
using namespace std;
const int inf=1e9;
int n,m,s,t;
int head[N],tot=2;
struct edge{
	int to,next,f,w;
}e[N*2];
void add(int u,int v,int f,int w)
{
	e[tot]=(edge){v,head[u],f,w};
	head[u]=tot++;
}
int flow,cost;
struct node{
	int x,w;
};
bool operator <(node a,node b){return a.w>b.w;}
priority_queue<node>q;
int h[N];
int sum[N];
int d[N],from[N],vis[N];
bool dij()
{
	memset(d,127/3,sizeof d);
	d[s]=0;
	sum[s]=inf;
	q.push((node){s,0});
	while(!q.empty())
	{
		node x=q.top();q.pop();
		if(vis[x.x]) continue;
		if(x.x==t) return 1;
		for(int i=head[x.x];i;i=e[i].next)
		{
			if(!e[i].f) continue;
			int v=e[i].to,w=e[i].w+h[x.x]-h[v]+x.w;
			if(d[v]>w) d[v]=w,from[v]=i,sum[v]=min(sum[x.x],e[i].f),q.push((node){v,w});
		}
	}
	return 0;
}
void updata()
{
	int w=sum[t],now=t;
	flow+=w;
	while(now^s)
	{
		int i=from[now];
		e[i].f-=w;
		e[i^1].f+=w;
		cost+=w*e[i].w;
		now=e[i^1].to;
	}
	for(int i=1;i<=n;i++) h[i]+=d[i];
}
int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v,f,w;
		scanf("%d%d%d%d",&u,&v,&f,&w);
		add(u,v,f,w);
		add(v,u,0,-w);
	}
	while(dij()) updata();
	printf("%d %d",flow,cost);
	return 0;
}
2024/7/19 11:35
加载中...