求助,dinicMLE了最后四个点
查看原帖
求助,dinicMLE了最后四个点
147670
金珂拉楼主2021/2/21 13:28
#include<bits/stdc++.h>
using namespace std;
int const N=5003;
int const inf=0x7f7f7f7f;
struct node {
	int v,nt;
	long long c,w;
} e[520010];
long long top=1,h[N],n,m,s,t,ans,d[N],cur[N],dis[N],cost,vis[N];
queue<int> q;
void add(int x,int y,int z,int p)
{
	e[++top].v=y;
	e[top].c=z;
	e[top].nt=h[x];
	e[top].w=p;
	h[x]=top;
	e[++top].v=x;
	e[top].c=0;
	e[top].nt=h[y];
	e[top].w=-p;
	h[y]=top;
}
int bfs()
{
	for(int i=1;i<=n;i++) dis[i]=inf;
	q.push(s);
	vis[s]=1;
	dis[s]=0;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=h[x];i;i=e[i].nt)
		{
			if(e[i].c>0 && dis[e[i].v]>dis[x]+e[i].w)
			{
			dis[e[i].v]=dis[x]+e[i].w;
			if(!vis[e[i].v]) 
			{
			q.push(e[i].v);
			vis[e[i].v]=1;
			}
			}
		}
	}
	return dis[t]!=inf;
}
int dfs(int now,int t,long long lim) {
    if(!lim || now==t) return lim;
    int flow=0;
    int f;
    for(int i=cur[now];i;i=e[i].nt) {
        cur[now]=i;
        if(dis[e[i].v]==dis[now]+e[i].w && (f=dfs(e[i].v,t,min(lim,e[i].c)))) {
            flow+=f;
            lim-=f;
            e[i].c-=f;
            e[i^1].c+=f;
            if(!lim) break;
        }
    }
    return flow;
}
void dinic()
{
	while(bfs())
	{
		memcpy(cur,h,sizeof(h));
		int f=dfs(s,t,inf);
		ans+=f;
		cost+=dis[t]*f;
	}
}
int main()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int x,y,z,p;
		cin>>x>>y>>z>>p;
			add(x,y,z,p);
	}
	dinic(); 
	cout<<ans<<' '<<cost;
	return 0;
}

EK太简单,zkw不会写,primal-dual没学过(,只能写dinic了

2021/2/21 13:28
加载中...