玄学全RE
查看原帖
玄学全RE
342076
Union_of_Britainschanghang楼主2021/3/7 22:35

第一个点在luoguIDE上都没问题,在这里就RE。。。

都是C++17

照着训练指南打的

#include<bits/stdc++.h>
using namespace std;//Dinic求最大流
struct Edge
{
	int from,to,cap,flow;//cap容量,flow流量 
};
const int maxn=205;
const int INF=2<<29;
struct Dinic
{
	int n,m,s,t;
	vector<Edge> edges;
	vector<int> G[maxn];
	bool vis[maxn];	
	int d[maxn];//层次相关 
	int cur[maxn];
	void AddEdge(int from,int to,int cap)
	{
		edges.push_back((Edge){from,to,cap,0});
		edges.push_back((Edge){from,to,0,0});//残量
		m=edges.size();
		G[from].push_back(m-2);
		G[to].push_back(m-1); 
	}
	bool BFS()
	{
		memset(vis,0,sizeof(vis));
		queue<int> Q;
		Q.push(s);//源点
		d[s]=0; 
		vis[s]=1;
		while(!Q.empty())
		{
			int x=Q.front();
            //cout<<x<<endl;
        	Q.pop();
			for(int i=0;i<G[x].size();i++)
			{
				Edge& e=edges[G[x][i]];
                //cout<<e.to<<endl;
				if(!vis[e.to]&&e.cap>e.flow)
				{
					vis[e.to]=1;
					d[e.to]=d[x]+1;
					Q.push(e.to);
				}
			}
		}
		return vis[t];//可以被访问到 
	}
	int DFS(int x,int a)
	{
		if(x==t||a==0)return a;
		int flow=0,f;
		for(int& i=cur[x];i<G[x].size();i++)//当前弧优化
		{
			Edge& e=edges[G[x][i]];
			if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
			{
				e.flow+=f;
				edges[G[x][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(a==0)break;	
			}	
		}
		return flow; 
	}
	int Maxflow(int s,int t)
	{
		this->s=s;
		this->t=t;
		int flow=0;
		while(BFS())
		{
            //cout<<"BFS"<<endl;
			memset(cur,0,sizeof(cur));
			flow+=DFS(s,INF);
		}
		printf("%d",flow);
	}
}; 
Dinic solve;
int main()
{
	cin>>solve.n>>solve.m>>solve.s>>solve.t;
    int rm=solve.m;
	for(int i=1;i<=rm;i++)
	{
		int x,y,l;
		cin>>x>>y>>l;
		solve.AddEdge(x,y,l);
	}
    //cout<<"Maxflow"<<endl;
	solve.Maxflow(solve.s,solve.t);
	return 0;
} ```
2021/3/7 22:35
加载中...