题目

题目大意

给你一个无向图，你要割掉一些边使得\(1\)到\(n\)的所有最短路径被阻截。

割掉一个边\((u,v)\)的代价为\(a_u\)或\(a_v\)（记为两种不同的方案）。

问最小代价及其唯一性。

思考历程

首先要将最短路图给建出来。

然后我就莫名其妙地想到了支配树，还在这个方向上思考了一阵子……

想不到怎么做……

然后我又想到之前某道题，将最大反链长度转化为最小链覆盖，然后用二分图匹配来实现。

我模仿着打了个KM算法，然后发现果然错了……

看来是不能直接生搬硬套的……

然后蓦然发现：这道题不就是个最小割吗！

于是就开始狂打……

最终的问题就是：如何判断唯一性……

匆匆忙忙地打了个错误的方法，交了上去。

正解

这题当然是最小割啦……

由于每条边选\(a_u\)和\(a_v\)算作两种方案，所以每条边要拆成两条来搞。

建图当然显然了。

至于判断是否有唯一性，可以把最小割后的残量网络的\(S\)集合和\(T\)集合找出来。

枚举\(S\)集合和\(T\)集合之间被割掉的边，求它们的权值和。

跟最小割进行对比，如果相等，则具有唯一性。

代码

using namespace std;

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <climits>

#include <vector>

#define N 410

#define M 4010

int n,m;

int a[N];

struct EDGE{

	int to,len;

	EDGE *las;

} e[M*2];

int ne;

EDGE *last[N*2];

inline void link(int u,int v,int len){

	e[ne]={v,len,last[u]};

	last[u]=e+ne++;

}

long long dis[N+M];

struct EDGE2{

	int to,c;

	EDGE2 *las;

} e2[M*4];

int ne2;

EDGE2 *last2[N+M];

#define rev(ei) (e2+(int(ei-e2)^1))

inline void link2(int u,int v,int c){

	e2[ne2]={v,c,last2[u]};

	last2[u]=e2+ne2++;

	e2[ne2]={u,0,last2[v]};

	last2[v]=e2+ne2++;

}

int S,T;

inline void S_P(){

	static int q[100001];

	static bool inq[N];

	int head=0,tail=1;

	q[1]=1;

	memset(inq,0,sizeof inq);

	inq[1]=1;

	memset(dis,127,sizeof dis);

	dis[1]=0;

	do{

		int x=q[++head];

		for (EDGE *ei=last[x];ei;ei=ei->las)

			if (dis[x]+ei->len<dis[ei->to]){

				dis[ei->to]=dis[x]+ei->len;

				if (!inq[ei->to]){

					inq[ei->to]=1;

					q[++tail]=ei->to;

				}

			}

		inq[x]=0;

	}

	while (head!=tail);

	memset(last2,0,sizeof last2);

	ne2=0;

	S=1,T=n;

	for (int i=1;i<=T;++i){

		for (EDGE *ei=last[i];ei;ei=ei->las)

			if (dis[i]+ei->len==dis[ei->to]){

				++n;

				link2(i,n,a[i]);

				link2(n,ei->to,a[ei->to]);

			}

	}

}

bool BZ;

int gap[N+M];

EDGE2 *cur[N+M];

int dfs(int x,int s){

	if (x==T)

		return s;

	int have=s;

	for (EDGE2 *ei=cur[x];ei;ei=ei->las){

		cur[x]=ei;

		if (ei->c && dis[ei->to]+1==dis[x]){

			int t=dfs(ei->to,min(ei->c,have));

			ei->c-=t,rev(ei)->c+=t,have-=t;

			if (!have)

				return s;

		}

	}

	cur[x]=last2[x];

	if (!--gap[dis[x]])

		BZ=0;

	dis[x]++;

	gap[dis[x]]++;

	return s-have;

}

inline long long flow(){

	long long res=0;

	memset(gap,0,sizeof gap);

	memset(dis,0,sizeof dis),

	gap[0]=n;

	BZ=1;

	while (BZ)

		res+=dfs(S,INT_MAX);

	return res;

}

inline bool pd(int mincut){

	static int q[N+M];

	static int vis[N+M];

	int head=0,tail=1;

	q[1]=S;

	memset(vis,0,sizeof vis);

	vis[S]=1;

	do{

		int x=q[++head];

		for (EDGE2 *ei=last2[x];ei;ei=ei->las)

			if (ei->c && !vis[ei->to]){

				vis[ei->to]=1;

				q[++tail]=ei->to;

			}

	}

	while (head!=tail);

	head=0,tail=1;

	q[1]=T;

	vis[T]=2;

	do{

		int x=q[++head];

		for (EDGE2 *ei=last2[x];ei;ei=ei->las)

			if (rev(ei)->c && !vis[ei->to]){

				vis[ei->to]=2;

				q[++tail]=ei->to;

			}

	}

	while (head!=tail);

	long long sum=0;

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

		for (EDGE2 *ei=last2[q[i]];ei;ei=ei->las)

			if (rev(ei)->c==0 && vis[ei->to]==1)

				sum+=ei->c;

	return sum==mincut;

}

int main(){

	freopen("in.txt","r",stdin);

//	freopen("out.txt","w",stdout);

	int T;

	scanf("%d",&T);

	while (T--){

		scanf("%d%d",&n,&m);

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

			scanf("%d",&a[i]);

		a[n]=INT_MAX;

		memset(last,0,sizeof last);

		ne=0;

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

			int u,v,len;

			scanf("%d%d%d",&u,&v,&len);

			link(u,v,len),link(v,u,len);

		}

		S_P();

		long long mincut=flow();

		if (pd(mincut))

			printf("Yes %d\n",mincut);

		else

			printf("No %d\n",mincut);

	}

	return 0;

}

总结

这题的最大收获就是唯一性的判定了……

巴特西

[JZOJ3348] 【NOI2013模拟】秘密任务

题目

题目大意

思考历程

正解

代码

总结

最新文章

热门文章