【dijkstra求助】tle+wa
查看原帖
【dijkstra求助】tle+wa
158000
滑不拉稽楼主2021/1/9 21:54
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register int 
typedef pair<int,int> Pair;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f==1?x:-x;
}
const int N=5e4+10,M=(5e5+10)*2,inf=0x3f3f3f3f;
int head[N],ver[M],nxt[M],flow[M],val[M],tot;
void add(int x,int y,int z,int w)
{
	ver[++tot]=y;flow[tot]=z;val[tot]=w;
	nxt[tot]=head[x];head[x]=tot;
}
int n,m,s,t,h[N],dis[N];
bool vis[N];
struct node{int v,edge;}pre[N];
priority_queue<Pair,vector<Pair>,greater<Pair> > q;
bool dijkstra()
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(pre,-1,sizeof(pre));
	dis[s]=0;q.push(make_pair(0,s));
	while(!q.empty())
	{
		int x=q.top().second;q.pop();
		if(vis[x])continue;
		vis[x]=true;
		for(re i=head[x];i;i=nxt[i])
		{
			int y=ver[i],z=val[i];
			int newcost=z+h[x]-h[y];
			if(flow[i] && dis[y]>dis[x]+newcost)
			{
				dis[y]=dis[x]+newcost;
				pre[y].v=x;pre[y].edge=i;
				if(y==t)return true;
				q.push(make_pair(dis[y],y));
			}
		}
	}
	return false;
}
Pair EK()
{
	int ans_flow=0,ans_cost=0;
	while(dijkstra())
	{
		int minn=inf;
		for(re i=t;i!=s;i=pre[i].v)
			minn=min(minn,flow[pre[i].edge]);
		for(re i=t;i!=s;i=pre[i].v)
		{
			flow[pre[i].edge]-=minn;
			flow[(pre[i].edge-1^1)+1]+=minn;
		}
		ans_flow+=minn;
		ans_cost+=minn*(dis[t]-h[s]+h[t]);
		for(re i=1;i<=n;++i) h[i]+=dis[i];
	}
	return make_pair(ans_flow,ans_cost);
}
signed main()
{
	//freopen("P3381_8.in","r",stdin);
	n=read(),m=read(),s=read(),t=read();
	for(re i=1;i<=m;++i)
	{
		int x=read(),y=read(),z=read(),w=read();
		add(x,y,z,w);add(y,x,0,-w);
	}
	Pair ans=EK();
	printf("%lld %lld\n",ans.first,ans.second);
	return 0;
}
2021/1/9 21:54
加载中...