「BZOJ1797」[Ahoi2009] Mincut 最小割

2015年4月7日10,4076

Description

A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题：问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？现在请你回答这两个问题。

Input

第一行有4个正整数，依次为N,M,s和t。第2行到第(M+1)行每行3个正整数v,u,c表示v中转站到u中转站之间有单向道路相连，单向道路的起点是v，终点是u,切断它的代价是c(1≤c≤100000)。注意:两个中转站之间可能有多条道路直接相连。同一行相邻两数之间可能有一个或多个空格。

Output

对每条单向边，按输入顺序，依次输出一行，包含两个非0即1的整数，分别表示对问题一和问题二的回答(其中输出1表示是，输出0表示否)。同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。

Sample Input

6 7 1 6
1 2 3
1 3 2
2 4 4
2 5 1
3 5 5
4 6 2
5 6 3

Sample Output

1 0
1 0
0 0
1 0
0 0
1 0
1 0

HINT

设第(i+1)行输入的边为i号边，那么{1,2},{6,7},{2,4,6}是仅有的三个最小代价切割方案。它们的并是{1,2,4,6,7}，交是。

「数据规模和约定」

测试数据规模如下表所示
数据编号 N M 数据编号 N M
1 10 50 6 1000 20000
2 20 200 7 1000 40000
3 200 2000 8 2000 50000
4 200 2000 9 3000 60000
5 1000 20000 10 4000 60000

题解

2014.5.26 TAT 写的bfs被叉了。。。

2015.4.7之前的做法存在一些问题，已更正

jcvb:

在残余网络上跑tarjan求出所有SCC，记id[u]为点u所在SCC的编号。显然有id[s]!=id[t]（否则s到t有通路，能继续增广）。

①对于任意一条满流边(u,v)，(u,v)能够出现在某个最小割集中，当且仅当id[u]!=id[v]；
②对于任意一条满流边(u,v)，(u,v)必定出现在最小割集中，当且仅当id[u]==id[s]且id[v]==id[t]。

①

<==将每个SCC缩成一个点，得到的新图就只含有满流边了。那么新图的任一s-t割都对应原图的某个最小割，从中任取一个把id[u]和id[v]割开的割即可证明。

②
<==：假设将(u,v)的边权增大，那么残余网络中会出现s->u->v->t的通路，从而能继续增广，于是最大流流量（也就是最小割容量）会增大。这即说明(u,v)是最小割集中必须出现的边。

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,S,T,cnt=1;
int last[4005],q[4005],h[4005],cur[4005];
int ind,top,scc;
int id[4005],dfn[4005],low[4005];
bool inq[4005];
struct edge{
	int from,to,next,v;
}e[120005];
void insert(int u,int v,int w)
{
	e[++cnt].from=u;e[cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].from=v;e[cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
bool bfs()
{
	int head=0,tail=1;
	for(int i=1;i<=n;i++)h[i]=-1;
	q[0]=S;h[S]=0;
	while(head!=tail)
	{
		int x=q[head];head++;
		for(int i=last[x];i;i=e[i].next)
			if(h[e[i].to]==-1&&e[i].v)
			{
				h[e[i].to]=h[x]+1;
				q[tail++]=e[i].to;
			}
	}
	return h[T]!=-1;
}
int dfs(int x,int f)
{
	if(x==T)return f;
	int w,used=0;
	for(int i=cur[x];i;i=e[i].next)
		if(h[e[i].to]==h[x]+1)
		{
			w=dfs(e[i].to,min(e[i].v,f-used));
			e[i].v-=w;e[i^1].v+=w;
			if(e[i].v)cur[x]=i;
			used+=w;if(used==f)return f;
		}
	if(!used)h[x]=-1;
	return used;
}
int dinic()
{
	int ans=0;
	while(bfs())
	{
		for(int i=1;i<=n;i++)cur[i]=last[i];
		ans+=dfs(S,inf);
	}
	return ans;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++ind;
	q[++top]=x;inq[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(e[i].v)
		{
			if(!dfn[e[i].to])
			{
				tarjan(e[i].to);
				low[x]=min(low[e[i].to],low[x]);
			}
			else if(inq[e[i].to])
				low[x]=min(dfn[e[i].to],low[x]);
		}
	int now=0;
	if(dfn[x]==low[x])
	{
		scc++;
		while(now!=x)
		{
			now=q[top--];
			id[now]=scc;inq[now]=0;
		}
	}
}
int main()
{
	n=read();m=read();S=read();T=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),w=read();
		insert(u,v,w);
	}
	dinic();
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	for(int i=2;i<=cnt;i+=2)
		if(e[i].v)puts("0 0");
		else 
		{
			if(id[e[i].from]!=id[e[i].to])
				printf("1 ");
			else printf("0 ");
			if(id[e[i].from]==id[S]&&id[e[i].to]==id[T])
				puts("1");
			else puts("0");
		}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,S,T,cnt=1;

int last[4005],q[4005],h[4005],cur[4005];

int ind,top,scc;

int id[4005],dfn[4005],low[4005];

bool inq[4005];

struct edge{

int from,to,next,v;

}e[120005];

void insert(int u,int v,int w)

{

e[++cnt].from=u;e[cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].from=v;e[cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;

}

bool bfs()

{

int head=0,tail=1;

for(int i=1;i<=n;i++)h[i]=-1;

q[0]=S;h[S]=0;

while(head!=tail)

{

int x=q[head];head++;

for(int i=last[x];i;i=e[i].next)

if(h[e[i].to]==-1&&e[i].v)

{

h[e[i].to]=h[x]+1;

q[tail++]=e[i].to;

}

return h[T]!=-1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

for(int i=cur[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=dfs(e[i].to,min(e[i].v,f-used));

e[i].v-=w;e[i^1].v+=w;

if(e[i].v)cur[x]=i;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

int dinic()

{

int ans=0;

while(bfs())

{

for(int i=1;i<=n;i++)cur[i]=last[i];

ans+=dfs(S,inf);

}

return ans;

}

void tarjan(int x)

{

dfn[x]=low[x]=++ind;

q[++top]=x;inq[x]=1;

for(int i=last[x];i;i=e[i].next)

if(e[i].v)

{

if(!dfn[e[i].to])

{

tarjan(e[i].to);

low[x]=min(low[e[i].to],low[x]);

}

else if(inq[e[i].to])

low[x]=min(dfn[e[i].to],low[x]);

}

int now=0;

if(dfn[x]==low[x])

{

scc++;

while(now!=x)

{

now=q[top--];

id[now]=scc;inq[now]=0;

}

int main()

{

n=read();m=read();S=read();T=read();

for(int i=1;i<=m;i++)

{

int u=read(),v=read(),w=read();

insert(u,v,w);

}

dinic();

for(int i=1;i<=n;i++)

if(!dfn[i])tarjan(i);

for(int i=2;i<=cnt;i+=2)

if(e[i].v)puts("0 0");

else

{

if(id[e[i].from]!=id[e[i].to])

printf("1 ");

else printf("0 ");

if(id[e[i].from]==id[S]&&id[e[i].to]==id[T])

puts("1");

else puts("0");

}

return 0;

}

« 「East!_XVI」九尾妖狐「BZOJ3996」[TJOI2015] 线性代数 »

hzwer

你看下楼下dwjshift的数据

_浅忆

哦…那如果两个中转站之间只有一条路就不用tarjan了？

YZ23

请问黄学长，这里的残余网络是否包括反向弧？若包含，SCC中的正向满流边的两端点可能会在一个SCC中吗？

hzwer

残余网络只包含有剩余流量的弧可能

dwjshift

这个做法似乎有问题0.0……你试试这组数据
4 4 1 4
1 2 1
2 3 1
2 3 1
3 4 1

hzwer

已更正

hzwer.com _ Home | http://hzwer.com

「BZOJ1797」[Ahoi2009] Mincut 最小割

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论