脚本宝典收集整理的这篇文章主要介绍了To_Heart—题解——BZOJ1791，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

Link

题解

我们先考虑一个无法再增广的残留网络中有什么性质

因为残留网络是由正向边和其对应的反向边组成的，那么对于 (x,y) 之间的某条边满流后，其对应的反向边一定有流量。

这时，如果 (x,y) 间另有一条非满流边，则 (x,y) 间构成一个强连通块。

然后我们考虑如果在一种方案中的一条边非满流，而这条边在其它方案中满流了，那么必会导致原方案中的某一条边由满流变为由非满流(如果它还是满流那么最大流就应该变大了)。

那么这两条边有什么性质呢？如果我们沿着增广路，可以发现这两条边应该在同一个强连通中

所以这道题我们就做完了：

首先我们需要判断它是不是满流，然后分类讨论：

对于存在于某种最小割方案中的边，我们只需要判断这条边的两端是否在同一个强连通里。

对于存在于任何最小割方案中的边，它的两端一定是一端和源点联通，一端和汇点联通的。

代码

#include<bITs/stdc++.h>
using namespace std;

const int INF=0x3f3f3f3f;

struct zz{
	int u,w,id,idid;
};
vector<zz> v[1000005];
map<int,bool> mp[60006];

struct Dinic{
	int dist[1000005],be[1000005];
	int s,t;
	void Add(int x,int y,int z,int id){
		int idx=v[x].size(),idy=v[y].size();
		v[x].push_back((zz){y,z,idy,id});
		v[y].push_back((zz){x,0,idx,id});
		mp[y][id]=1;
	}
	bool BFS(){
		bool f=0;memset(dist,-1,sizeof dist);
		queue<int> q;q.push(s);
		dist[s]=be[s]=0;
		while(!q.empty()){
			int x=q.front();q.pop();
			int siz=v[x].size();
			for(int i=0;i<siz;i++){
				int y=v[x][i].u,w=v[x][i].w;
				if(!w||dist[y]!=-1) continue;
				q.push(y),be[y]=0,dist[y]=dist[x]+1;
				if(y==t) f=1;
			}
		}
		return f;
	}
	int DFS(int x,int sum){
		if(x==t||!sum) return sum;
		int siz=v[x].size(),ans=0;
		for(int i=be[x];i<siz&&sum!=ans;i++){
			int y=v[x][i].u,w=v[x][i].w,id=v[x][i].id;be[x]=i;
			if(!w||dist[x]!=dist[y]-1) continue;
			int now=DFS(y,min(sum-ans,w));
			if(!now) dist[y]=0;
			v[x][i].w-=now,v[y][id].w+=now,ans+=now;
		}
		return ans;
	}
	int dinic(){
		int ans=0,now=0;
		while(BFS()) while(now=DFS(s,INF)) ans+=now;
		return ans;
	}
}T;

int n,m;
bool f[600005];
bool FLAG[600006];
bool vis[600006];                      
struct ss{
	int x,y;
}a[100000];

int col[100005];
int DFSN[100005],Low[100005];

struct TarJan{
	bool qwq[100005];
	int tot=0,qwqtot=0;
	stack<int> st;
	void Tarjan(int x){
		DFSN[x]=Low[x]=++tot;
		st.push(x);qwq[x]=1;
		for(int i=0;i<v[x].size();i++){
			int y=v[x][i].u;
			if(!v[x][i].w) continue;
			if(!DFSN[y]) Tarjan(y),Low[x]=min(Low[x],Low[y]);
			else if(qwq[y]) Low[x]=min(Low[x],DFSN[y]);
		}
		if(DFSN[x]==Low[x]){
			int now;++qwqtot;
			do{
				now=st.top();st.pop();
				qwq[now]=0,col[now]=qwqtot;
			}while(x!=now);
		}
	}
}xf;

int main(){
	cin>>n>>m>>T.s>>T.t;
	for(int i=1,x,y,z;i<=m;i++){
		scanf("%d%d%d",&amp;x,&y,&z);
		T.Add(x,y,z,i);
	}
	int ans=T.dinic();
	for(int i=1;i<=n;i++) if(!DFSN[i]) xf.Tarjan(i);
	for(int x=1;x<=n;x++){
		for(int i=0;i<v[x].size();i++){
			int y=v[x][i].u,id=v[x][i].idid;
			if(v[x][i].w) continue;
			if(mp[x][id]) continue;
			if(col[x]!=col[y]) f[id]=1;
			if(col[x]==col[T.s]&&col[y]==col[T.t]) FLAG[id]=1;
		}
	} 
	for(int i=1;i<=m;i++) PRintf("%d %dn",f[i],FLAG[i]);
	return 0;
}

脚本宝典总结

以上是脚本宝典为你收集整理的To_Heart—题解——BZOJ1791全部内容，希望文章能够帮你解决To_Heart—题解——BZOJ1791所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。