BZOJ1266 [AHOI2006]上学路线route Floyd 最小割 SAP

时间：2022-05-21 08:19:14

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

题目传送门 - BZOJ1266

题意概括

　　一个无向图，第一问：从1~n的最短路。

　　第二问，删除价值总和最小的边，使得1~n的最短路变长。

题解

　　第一问floyd跑一跑就可以了。

　　第二问，最小割就可以了。

　　最小割相关可以看这里（往后翻就有）。

代码

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=500+5,M=130000;

int n,m,dis[N][N];

struct Read_E{

	int x,y,t,c;

}e[M];

struct Edge{

	int x,y,cap,flow,nxt;

};

struct Gragh{

	static const int Inf=1<<28;

	int cnt,fst[N],dist[N],s,t,num[N],cur[N],p[N],q[N],head,tail;

	Edge e[M*4];

	void set(int S,int T){

		s=S,t=T,cnt=1;

		memset(fst,0,sizeof fst),memset(e,0,sizeof e);

	}

	void add(int a,int b,int c){

		e[++cnt].x=a,e[cnt].y=b,e[cnt].cap=c,e[cnt].flow=0;

		e[cnt].nxt=fst[a],fst[a]=cnt;

		e[++cnt].x=b,e[cnt].y=a,e[cnt].cap=0,e[cnt].flow=0;

		e[cnt].nxt=fst[b],fst[b]=cnt;

	}

	void re_bfs(){

		memset(dist,-1,sizeof dist);

		head=tail=dist[t]=0,q[++tail]=t;

		while (head<tail)

			for (int x=q[++head],i=fst[x];i;i=e[i].nxt)

				if (e[i].cap==0&&dist[e[i].y]==-1)

					dist[q[++tail]=e[i].y]=dist[x]+1;

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

			if (dist[i]==-1)

				dist[i]=n+1;

	}

	int Augment(int &point){

		int ex_Flow=Inf;

		for (int i=t;i!=s;i=e[p[i]].x)

			if (e[p[i]].cap-e[p[i]].flow<=ex_Flow)

				ex_Flow=e[p[i]].cap-e[p[i]].flow,point=e[p[i]].x;

		for (int i=t;i!=s;i=e[p[i]].x)

			e[p[i]].flow+=ex_Flow,e[p[i]^1].flow-=ex_Flow;

		return ex_Flow;

	}

	int SAP(){

		int x=s,y,MaxFlow=0;

		memset(num,0,sizeof num);

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

			cur[i]=fst[i],num[dist[i]]++;

		while (dist[s]<=n){

			if (x==t){

				MaxFlow+=Augment(x);

				continue;

			}

			bool found=0;

			for (int i=cur[x];i!=0&&!found;i=e[i].nxt)

				if (dist[e[i].y]+1==dist[x]&&e[i].cap>e[i].flow)

					p[e[i].y]=cur[x]=i,x=e[i].y,found=1;

			if (found)

				continue;

			int d=n+1;

			for (int i=fst[x];i;i=e[i].nxt)

				if (e[i].cap>e[i].flow)

					d=min(d,dist[e[i].y]+1);

			if (!(--num[dist[x]]))

				return MaxFlow;

			num[dist[x]=d]++,cur[x]=fst[x];

			if (x!=s)

				x=e[p[x]].x;

		}

		return MaxFlow;

	}

}g;

int main(){

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

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

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

			dis[i][j]=1<<28;

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

		dis[i][i]=0;

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

		int x,y,t,c;

		scanf("%d%d%d%d",&x,&y,&t,&c);

		e[i].x=x,e[i].y=y,e[i].t=t,e[i].c=c;

		dis[x][y]=min(dis[x][y],t);

		dis[y][x]=min(dis[y][x],t);

	}

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

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

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

				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

	g.set(1,n);

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

		int x=e[i].x,y=e[i].y,t=e[i].t,c=e[i].c;

		if (dis[1][n]==dis[1][x]+t+dis[y][n])

			g.add(x,y,c);

		if (dis[1][n]==dis[1][y]+t+dis[x][n])

			g.add(y,x,c);

	}

	g.re_bfs();

	printf("%d\n%d",dis[1][n],g.SAP());

	return 0;

}

　　

相关文章