一个神秘的oj2093 花园的守护之神（最小割）

给定一张无向图，你每次可以将一条路的权值增加1，询问最少增加多少次才会使得\(s->t\)的最短路改变

QwQ一看到这个题，我就用种最小割的感觉

我们可以把最短路上的点取出来，然后做最小割呀！！

首先

我们将最短路求一下\(dis[i]\)表示\(s\)到\(i\)的最短距离，\(disn[i]\)表示\(t\)到\(i\)的最短路。

如果一条边\(u->v\)

满足\(dis[u]+val[i]+disn[v]==dis[t]\)

那么他就是最短路上的边了。

这里注意要将双向边看成两个单向边来做，不然会出bug

上代码

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#define pa pair<long long,long long>

#define ll long long

using namespace std;

inline int read()

{

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

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

inline ll read1()

{

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

  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}

  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

  return x*f;

}

const int maxm = 2e6+1e2;

const int maxn = 1010;

const int inf = 2e9;

int point[maxn],nxt[maxm],to[maxm];

ll val[maxm];

int cnt,n,m;

int x[maxm],y[maxm];

ll w[maxm];

ll dis[maxn];

int vis[maxn];

ll disn[maxn];

int h[maxn];

int s,t;

queue<int> q;

priority_queue<pa,vector<pa>,greater<pa> > que;

void addedge(int x,int y,ll w)

{

	nxt[++cnt]=point[x];

	to[cnt]=y;

	val[cnt]=w;

	point[x]=cnt;

}

void insert(int x,int y,ll w)

{

	addedge(x,y,w);

	addedge(y,x,0);

}

void init()

{

  cnt=1;

  memset(point,0,sizeof(point));

}

bool bfs(int s)

{

	memset(h,-1,sizeof(h));

	h[s]=0;

	q.push(s);

	while (!q.empty())

	{

		int x = q.front();

		q.pop();

		for (int i=point[x];i;i=nxt[i])

		{

			int p = to[i];

			if (val[i]>0 && h[p]==-1)

			{

				h[p]=h[x]+1;

				q.push(p);

			}

		}

	}

	if (h[t]==-1) return 0;

	else return 1;

}

int dfs(int x,int low)

{

	if (x==t || low==0) return low;

	int totflow=0;

	for (int i=point[x];i;i=nxt[i])

	{

		int p = to[i];

		if (val[i]>0 && h[p]==h[x]+1)

	    {

	    	int tmp = dfs(p,min(low,(int)val[i]));

	    	val[i]-=tmp;

	    	val[i^1]+=tmp;

	    	low-=tmp;

	    	totflow+=tmp;

	        if (low==0) return totflow;

		}

	 }

	 if (low>0) h[x]=-1;

	 return totflow;

}

int dinic()

{

	int ans=0;

	while (bfs(s))

	{

		ans=ans+dfs(s,inf);

	}

	return ans;

}

void dijkstra(int s)

{

	memset(vis,0,sizeof(vis));

    memset(dis,127/3,sizeof(dis));

	dis[s]=0;

	//vis[s]=1;

	que.push(make_pair(0,s));

	while (!que.empty())

	{

		int x = que.top().second;

		que.pop();

		if (vis[x]) continue;

		vis[x]=1;

		for (register int i=point[x];i;i=nxt[i])

		{

			int p = to[i];

			if (dis[p]>dis[x]+val[i])

			{

				dis[p]=dis[x]+val[i];

				que.push(make_pair(dis[p],p));

			}

		}

	}

}

void dijkstran(int s)

{

	memset(vis,0,sizeof(vis));

    memset(disn,127/3,sizeof(disn));

	disn[s]=0;

	//vis[s]=1;

	que.push(make_pair(0,s));

	while (!que.empty())

	{

		int x = que.top().second;

		que.pop();

		if (vis[x]) continue;

		vis[x]=1;

		for (register int i=point[x];i;i=nxt[i])

		{

			int p = to[i];

			if (disn[p]>disn[x]+val[i]){

				disn[p]=disn[x]+val[i];

				que.push(make_pair(disn[p],p));

			}

		}

	}

}

int main()

{

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

  freopen("greendam2002.out","w",stdout);

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

  for (register int i=1;i<=m;i++) x[i]=read(),y[i]=read(),w[i]=read1();

  for (register int i=1;i<=m;i++) addedge(x[i],y[i],w[i]),addedge(y[i],x[i],w[i]);

  dijkstra(s);

  dijkstran(t);

  init();

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

  {

  	 if (dis[t]==dis[x[i]]+w[i]+disn[y[i]])

  	 {

  	    insert(x[i],y[i],1);

	 }

	 if(dis[t]==dis[y[i]]+w[i]+disn[x[i]])

	 {

	 	insert(y[i],x[i],1);

	 }

  }

  cout<<dinic();

  return 0;

}

巴特西

一个神秘的oj2093 花园的守护之神（最小割）

最新文章

热门文章