萌新刚会开机,求奆佬捉虫qwq
查看原帖
萌新刚会开机,求奆佬捉虫qwq
146837
吴铭轼楼主2020/5/28 21:40
#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
#include <cmath>
#include <string>
#include <cstring>
#include <vector>
#include <cstdio>
using namespace std;
int n,m,S,T;
struct zdq{
	int v,w,f,nxt;
}e[100005];
int head[5003],cnt=1;
void add(int u,int v,int w,int f)
{
	e[++cnt].v=v;
	e[cnt].f=f;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
 } 
int vis[5003],dis[5003],pre[5003],incf[5003],last[5003];
bool spfa(){
	queue<int> q;
	memset(dis,2147483647,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[S]=0,vis[S]=1;
	q.push(S); 
	incf[S]=2147483647;
	while(q.size() )
	{
		int u=q.front();
		vis[u]=0;
		q.pop();
		cout<<u<<endl;
		for(int i=head[u];i;i=e[i].nxt )
		{
			if(!e[i].w )
			continue;
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].f )
			{
				cout<<v;
				dis[v]=dis[u]+e[i].f;
				incf[v]=min(incf[u],e[i].w );
				pre[v]=i;
				last[v]=u;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v); 
				}
			}
		 } 
	}
	if(dis[T]==2147483647)
	return 0;
	return 1;
}
long long ans1=0,ans2=0;
void update(){
	int x=T;
	while(x!=S)
	{
		int i=pre[x];
		e[i].w-=incf[T];
		e[i^1].w+=incf[T];
		x=last[x];
	}
	ans1+=incf[T];
	ans2+=dis[T]*incf[T];
}
int main()
{
	cin>>n>>m>>S>>T;
	for(int i=1;i<=m;i++)
	{
		int u,v,w,f;
		cin>>u>>v>>w>>f;
		add(u,v,w,f);
		add(v,u,0,-f);
	}
	while(spfa())
	update();
	cout<<ans1<<" "<<ans2; 
	return 0;
}

2020/5/28 21:40
加载中...