求助样例不过
查看原帖
求助样例不过
663638
Butterfly_qwq楼主2023/4/23 20:06
#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int to,next,f,c;
}e[114514];
int ans1,ans2,n,m,s,t,cnt=-1,head[5001],vis[5001],dis[5001],mnw[5001],pre[5001];
void add(int u,int v,int w,int c)
{
	e[++cnt]=(edge){v,head[u],w,c};
	head[u]=cnt;
	e[++cnt]=(edge){u,head[v],0,-c};
	head[v]=cnt;
}
bool spfa()
{
	queue<int> q;
	q.push(s);
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(mnw,0x3f,sizeof(mnw));
	dis[s]=0;
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].next)
		{
			int v=e[i].to,f=e[i].f,c=e[i].c;
			if(f>0&&c+dis[u]<dis[v])
			{
				dis[v]=c+dis[u];
				mnw[v]=min(mnw[u],f);
                pre[v]=i;
                if(!vis[v])
                {
                	vis[v]=1;
                	q.push(v);
				}
				if(v==t)return true;
			}
		}
	}
	return false;
}
void update()
{
	int u=t;
	while(u!=s)
	{
		int v=pre[u];
		e[v].f-=mnw[t];
		e[v^1].f+=mnw[t];
		u=e[v^1].to;
	}
	ans1+=mnw[t];
	ans2+=mnw[t]*dis[t];
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
	int u,v,w,c;
	cin>>n>>m>>s>>t;
	for(int i=0;i<m;i++)
	{
		cin>>u>>v>>w>>c;
		add(u,v,w,c);
	}
	while(spfa())update();
	cout<<ans1<<' '<<ans2;
	return 0;
}
2023/4/23 20:06
加载中...