求助dinic(后4个点wa)63分
查看原帖
求助dinic(后4个点wa)63分
360279
ytcfghyeee楼主2023/11/14 15:57
#include<iostream>
#include<cstdio> 
#include<algorithm>
#include<cstring>
#include<vector>
#include<bitset>
#include<queue>
#define N 5205
#define M 120005
#define X 12147483647
#define mn(a,b) (((a)<(b))?(a):(b))
#define pf printf
#define int long long 
using namespace std;
inline int re(){int ff=0;bool fu=false;char ch=getchar();while(ch<'0'||ch>'9')fu|=(ch=='-'),ch=getchar();while('0'<=ch&&ch<='9')ff=(ff<<3)+(ff<<1)+(ch^'0'),ch=getchar();return fu?-ff:ff;}
struct xy {int u,v,flw,w;};
int n,m,s,t;
struct dinic{
    int cur[N],dis[N];
    queue<int> que;
    bitset<N> vis,ins;
    vector<xy> e;
    vector<int> vt[N];
    void addl(int u,int v,int fw,int w){
        e.push_back((xy){u,v,fw,w});
        e.push_back((xy){v,u,0,w});
        int n1=e.size()-2;
        vt[u].push_back(n1);
        vt[v].push_back(n1+1);
    }
    inline bool bfs(){
        xy E;vis=0;ins=0;
        register int i;
		for(i=1;i<=n;++i) dis[i]=0x3f3f3f3f;
        que.push(s);dis[s]=0;vis[s]=1;ins[s]=1;
        int l=1,r=1,u,vl;
        while(!que.empty()){
            u=que.front(); que.pop();ins[u]=0;
			vl=vt[u].size();
            for(i=0;i<vl;++i){
            	int io=vt[u][i];
                E=e[io];
                if (e[io].flw&&dis[E.v]>dis[u]+E.w){
                	dis[E.v]=dis[u]+E.w;
					if(!ins[E.v])que.push(E.v);
					ins[E.v]=1;
                    vis[E.v]=1;
                }
            }
        }
        return vis[t];
    }
    int dfs(int u,int a,int &w){
        if (u==t||!a) return a;
        xy E;int vl=vt[u].size(),sf=0,flw;
        for(register int &i=cur[u];i<vl;++i){
        	int io=vt[u][i];
            E=e[io];
            if (vis[E.v]==1&&dis[E.v]==dis[E.u]+E.w&&(flw=dfs(E.v,mn(E.flw,a),w))!=0){
                sf+=flw;
				a-=flw;
				if(io&1){
					w-=flw*E.w;
					pf("#");
				}
				else w+=flw*E.w;
                e[io].flw-=flw;
                e[io^1].flw+=flw;
                if (!a) break;
            }
        }return sf;
    }
    void work(){
        int flw=0,ans=0,cw;register int i;
        while(bfs()){
        	for(i=1;i<=n;++i)cur[i]=0;
            cw=0;
            flw+=dfs(s,X,cw);
            ans+=cw;
        }
		pf("%lld %lld",flw,ans);
		return ;
    }
}sol;
signed main(){
	freopen("1.in","r",stdin);
	int ans=0;
    n=re();m=re();s=re();t=re();
    int x,y,z,w;
    for(register int i=0;i<m;++i){
    	x=re();
    	y=re();
    	z=re();
    	w=re();
    	sol.addl(x,y,z,w);
	}
	sol.work();
    return 0; 
} 
2023/11/14 15:57
加载中...