社区讨论

求助!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 条回复,欢迎继续交流。

正在加载回复...