1 条题解

  • 0
    @ 2026-2-7 20:04:29
    #include<bits/stdc++.h>
    #define INF INT_MAX
    using namespace std;
    const int N=5e4+10,M=2.5e5+10;
    int n,m,st,ed,S,T;
    struct edge{
    	int x,y,c,pre;
    }a[M*2];
    int alen,last[N],cur[N];
    void ins(int x,int y,int c)
    {
    	a[++alen]={x,y,c,last[x]};
    	last[x]=alen;
    }
    int f[N],h[N];
    bool bfs()
    {
    	memset(h,0,sizeof(h));h[S]=1;
    	deque<int> q;q.push_back(S);
    	while(!q.empty())
    	{
    		int x=q.front();q.pop_front();
    		for(int k=last[x];k;k=a[k].pre)
    		{
    			int y=a[k].y;
    			if(!h[y]&&a[k].c)
    			{
    				h[y]=h[x]+1;
    				q.push_back(y);
    			}
    		}
    	}
    	return h[T];
    }
    int Dinic(int x,int f)
    {
    	if(x==T) return f;
    	int sx=0;
    	for(int k=cur[x];k;k=a[k].pre)
    	{
    		cur[x]=k;
    		int y=a[k].y;
    		if(h[y]==h[x]+1&&a[k].c&&sx<f)
    		{
    			int sy=Dinic(y,min(a[k].c,f-sx));
    			a[k].c-=sy,a[k^1].c+=sy;
    			sx+=sy;
    			if(sx==f) break;
    		}
    	}
    	if(sx==0) h[x]=0;
    	return sx;
    }
    int main()
    {
    	scanf("%d%d%d%d",&n,&m,&st,&ed);
    	S=n+1,T=n+2;
    	alen=1;memset(last,0,sizeof(last));
    	for(int i=1;i<=m;i++)
    	{
    		int x,y,u,v;
    		scanf("%d%d%d%d",&x,&y,&u,&v);
    		ins(x,y,v-u),ins(y,x,0);
    		f[x]-=u,f[y]+=u;
    	}
    	int sum1=0,sum2=0;
    	for(int i=1;i<=n;i++)
    	{
    		if(f[i]>0) ins(S,i,f[i]),ins(i,S,0),sum1+=f[i];
    		if(f[i]<0) ins(i,T,-f[i]),ins(T,i,0);
    	}
    	ins(ed,st,INF),ins(st,ed,0);
    	while(bfs())
    	{
    		memcpy(cur,last,sizeof(last));
    		sum2+=Dinic(S,INF);
    	}
    	if(sum1^sum2) puts("please go home to sleep");
    	else
    	{
    		for(int k=last[S];k;k=a[k].pre) a[k].c=a[k^1].c=0;
    		for(int k=last[T];k;k=a[k].pre) a[k].c=a[k^1].c=0;
    		sum2=a[alen].c;
    		a[alen].c=a[alen-1].c=0;
    		S=ed,T=st;int sum3=0;
    		while(bfs())
    		{
    			memcpy(cur,last,sizeof(last));
    			sum3+=Dinic(S,INF);
    		}
    		printf("%d\n",sum2-sum3);
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    385
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    26
    已通过
    11
    上传者