「BZOJ3258」秘密任务 - 最小割唯一性判定

题目大意

    Alice听说在一片神奇的大陆MagicLand，有一个古老的传说……
    很久很久以前，那个时候 MagicStates共和国刚刚成立。 反对新政府的势力虽已被镇压，但仍然在暗地活动。这一次，情报局得到了一个令人震惊的消息，被软禁在首都府邸中的Frank ——著名的反对派领袖，秘密逃出首都，去往反对派的大本营。根据相关的情报，Frank计划通过城市之间 发达的高速公路，经过最短的路程抵达目的地。不妨将 MagicStates共和国简化为由$N$个城市,$M$条高速公路构成的连通的无向图，首都为城市$1$，反对派的大本营为城市$N$。
    每条高速公路连接两个不同的城市，且路程是已知的。而Frank选择了一条从城市$1$到城市$N$的最短路径作为他的逃跑路线。为了阻止Frank，共和国总统决定在某些城市的高速公路的出入口设立检查点，在Frank经过检查点时将他逮捕。
    举例来说，如果有一条高速公路连接城市$u$和城市$v$，在这条公路的城市$u$或城市$v$的出入口设立检查点，那么Frank经过高速公路时就会被发现。特别的是，由于城市$N$实际上处在反对派的控制下，所以不能在城市$N$设立检查点。
    然而在任何城市设立检查点都需要一定的费用。更具体的，若在城市$u$设立$k$个检查点，就要花费$A_u$乘以$k$的代价，其中$A_u$是城市$u$的相关参数。值得注意的是，这个代价与这$k$个检查点具体设在哪些公路的出入口无关,于是，总统责令情报局拟定一个方案，花费最小的代价使得无论Frank选择哪条最短路线，都会在（除城市$N$以外）某个城市的高速公路出入口被发现。读到这里，Alice很想知道阻止Frank所需要花费的最小代价，并且她还希望知道最优方案是否是唯一的。只好再请你帮助她了。
    注意，我们称两个方案不同当且仅当存在某城市$k$，两种方案中在城市$k$的检查点的设置（而不仅是数目）是不同的。
    注意，输入文件包含多组测试数据。

---

题目分析

先跑两次最短路将网络流图建出来。
注意每条边需要拆点，因为这条边可以割两个位置，且影响唯一性。
然后跑一次最小割。

接下来需要做的是判定最小割的唯一性。
以前的方法是用两次DFS判断S集合与T集合是否有交集。
然而这道题有重边，因此不能使用这种方法，下面我们来考虑新的方法。

必要（关键）割边

在最小割集中必定出现的边称为必要割边，或关键割边。
判定关键割边的方法：
若可以分别从$S,T$到达$a,b$，则$a\rightarrow b$为关键割边。
正确性是显然的。

可能割边

在最小割集中可能出现的边称为可能割边。
判定可能割边的方法：
将残余网络用Tarjan缩点，若一条正向边跨越不同强连通分量且满流，则其为可能割边。
正确性：这条边连通两个强连通分量，且有流量，说明流量可以且必须通过此边到达T，又因为满流，因此必定能够找到一个割集包含此边。

最小割唯一性判定

有了以上两个定义，我们就可以判定最小割的唯一性了。
若所有的可能割边都是必要割边，则最小割唯一。
将残余网络用Tarjan缩点，若一条正向边跨越不同强连通分量且满流，且不刚好跨越$S,T$所在强连通分量，则最小割不唯一。

然后就可以完成此题了。

---

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

inline int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
	while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
	return num*bj;
}

const int maxn=4505;

struct Edge {int from,to,dist;};

int n,m,top=0,step=0,BCC=0,cnt=0,a[maxn],Belong[maxn],Dfn[maxn],Lowlink[maxn],Stack[maxn];
LL dist1[maxn],dist2[maxn];
bool vst[maxn],Instack[maxn];
vector<Edge> edges[maxn];

void Clear() {
	step=BCC=0;
	for(int i=1; i<=cnt; i++) {
		edges[i].clear();
		Dfn[i]=0;
	}
}

#define pii pair<LL,int>

void Dijkstra(int s,LL *dist) {
	fill(dist,dist+n+1,LLONG_MAX/2),fill(vst,vst+n+1,0);
	priority_queue<pii,vector<pii>,greater<pii> > Q;
	Q.push(pii(dist[s]=0,s));
	while(!Q.empty()) {
		int Now=Q.top().second;
		Q.pop();
		if(vst[Now])continue;
		vst[Now]=1;
		for(Edge &e:edges[Now]) {
			int Next=e.to;
			if(dist[Next]>dist[Now]+e.dist) {
				dist[Next]=dist[Now]+e.dist;
				Q.push(pii(dist[Next],Next));
			}
		}
	}
}

struct Dinic {
	struct Edge {
		int from,to;
		LL cap,flow;
		Edge(int x=0,int y=0,LL c=0,LL f=0):from(x),to(y),cap(c),flow(f) {}
	};
	int n,m,s,t;
	vector<Edge> edges;
	vector<int> G[maxn];
	bool vst[maxn];
	int dist[maxn],cur[maxn];
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,LL v) {
		edges.push_back(Edge(x,y,v,0));
		edges.push_back(Edge(y,x,0,0));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bfs() {
		fill(vst+1,vst+n+1,0);
		queue<int> Q;
		Q.push(t); //reversed
		vst[t]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(!vst[Next]&&e.cap>e.flow) { 
					vst[Next]=1;
					dist[Next]=dist[Now]+1;
					if(Next==s)return 1;
					Q.push(Next);
				}
			}
		}
		return vst[s];
	}
	LL dfs(int Now,LL a) {
		if(Now==t||a==0)return a;
		LL flow=0;
		for(int& i=cur[Now]; i<G[Now].size(); i++) {
			Edge& e=edges[G[Now][i]];
			int Next=e.to;
			if(dist[Now]-1!=dist[Next])continue;
			LL nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				e.flow+=nextflow;
				edges[G[Now][i]^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	LL maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		LL flow=0;
		while(bfs()) {
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,LLONG_MAX);
		}
		return flow;
	}
} dinic;

void Tarjan(int Now) {
	Dfn[Now]=Lowlink[Now]=++step;
	Stack[++top]=Now;
	Instack[Now]=1;
	for(int id:dinic.G[Now]) {
		auto &e=dinic.edges[id];
		if(e.flow==e.cap)continue;
		int Next=e.to;
		if(!Dfn[Next]) {Tarjan(Next);Lowlink[Now]=min(Lowlink[Now],Lowlink[Next]);}
		else if(Instack[Next])Lowlink[Now]=min(Lowlink[Now],Dfn[Next]);
	}
	if(Dfn[Now]==Lowlink[Now]) {
		BCC++;
		int y;
		do {
			y=Stack[top--];
			Belong[y]=BCC;
			Instack[y]=0;
		} while(y!=Now);
	}
}

int main() {
	int t=Get_Int();
	while(t--) {
		Clear();
		n=Get_Int();
		m=Get_Int();
		for(int i=1; i<n; i++)a[i]=Get_Int();
		a[n]=INT_MAX;
		for(int i=1; i<=m; i++) {
			int x=Get_Int(),y=Get_Int(),v=Get_Int();
			edges[x].push_back((Edge) {x,y,v});
			edges[y].push_back((Edge) {y,x,v});
		}
		Dijkstra(1,dist1);
		Dijkstra(n,dist2);
		dinic.init(cnt);
		cnt=n;
		for(int Now=1; Now<n; Now++)
			for(Edge &e:edges[Now]) {
				int Next=e.to;
				if(dist1[n]==dist1[Now]+e.dist+dist2[Next]) {
					cnt++; //!!!
					dinic.AddEdge(Now,cnt,a[Now]);
					dinic.AddEdge(cnt,Next,a[Next]);
				}
			}
		dinic.n=cnt;
		LL ans=dinic.maxflow(1,n);
		for(int i=1; i<=cnt; i++)if(!Dfn[i])Tarjan(i);
		bool bj=1;
		for(auto &e:dinic.edges) {
			int x=e.from,y=e.to;
			if(!e.cap||e.cap!=e.flow||Belong[x]==Belong[y]||(Belong[x]==Belong[1]&&Belong[y]==Belong[n]))continue;
			printf("No %lld\n",ans);
			bj=0;
			break;
		}
		if(bj)printf("Yes %lld\n",ans);
	}
	return 0;
}