社区讨论
求助!73分!!
P3381【模板】最小费用最大流参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6offqg
- 此快照首次捕获于
- 2025/11/20 08:12 4 个月前
- 此快照最后确认于
- 2025/11/20 08:12 4 个月前
C
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define inf 2147483640
#define maxn 5010
#define maxm 50010
using namespace std;
int n,m,s,t;
int head[maxn],to[maxm*2],nxt[maxm*2],c[maxm*2],v[maxm*2],tot=1;
void add(int u,int z,int x,int y)
{
tot++;
nxt[tot]=head[u];
head[u]=tot;
to[tot]=z;
c[tot]=x;
v[tot]=y;
}
int sum;
int ans=0;
queue<int> q;
int dis[maxn],pre[maxn],book[maxn],pre_num[maxn];
int spfa()
{
memset(book,0,sizeof(book));
while(q.size()!=0) q.pop();
for(int i=1;i<=n;i++) dis[i]=inf;
dis[s]=0;
for(int i=1;i<=n;i++) pre[i]=0;
q.push(s);
book[s]=1;
while(q.size()!=0)
{
int now=q.front();
q.pop();
for(int i=head[now];i!=0;i=nxt[i])
{
if(dis[to[i]]>dis[now]+v[i]&&c[i]>0)
{
pre[to[i]]=now;
pre_num[to[i]]=i;
dis[to[i]]=dis[now]+v[i];
if(book[to[i]]==0) {q.push(to[i]);book[to[i]]=1;}
}
}
}
if(dis[t]==inf) return 0;
int di=inf;
for(int i=t;i!=s;i=pre[i]) di=min(di,c[pre_num[i]]);
for(int i=t;i!=s;i=pre[i]) {c[pre_num[i]]-=di;c[pre_num[i]^1]+=di;};
for(int i=t;i!=s;i=pre[i]) sum+=v[pre_num[i]]*di;
//sum+=dis[t]*di;
return di;
}
void dinic()
{
while(int d=spfa()) ans+=d;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
int q,w,e,r;
scanf("%d%d%d%d",&q,&w,&e,&r);
add(q,w,e,r);
add(w,q,0,-r);
}
dinic();
printf("%d %d\n",ans,sum);
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...