Description

link

题意概述：给一张图，每条边有边权，求让点 \(1\) 和点 \(n\) 不连通的“最小破坏边权和” 和 “在此基础上的最小破坏边数”

边数 \(\leq 1000\) ，点数 \(\leq 32\)

Solution

\[Begin
\]

其实看出来这个可以用最小割做挺显然的

然后第二问的做法就有点点技巧了

我们把图中的每一条边的边权 \(w_i\) 转化成 \(a \times w_i+1\)

其中\(a\) > \(1000\)

然后我们跑最大流，求得的 \(ans/a\) 就是最小割，然后 \(ans \% a\) 就是边数

这里特别好理解的

\[Finish
\]

Code

#include<bits/stdc++.h>

using namespace std;

#define int long long

namespace yspm{

	inline int read()

	{

		int res=0,f=1; char k;

		while(!isdigit(k=getchar())) if(k=='-') f=-1;

		while(isdigit(k)) res=res*10+k-'0',k=getchar();

		return res*f;

	}

	const int N=1e4+10,M=1e5+10;

	struct node{int nxt,to,lim;}e[M<<1];

	int head[N],dep[N],ans,s,t,cnt=1,n,m,a=1002;

	inline void add(int u,int v,int w)

	{

		e[++cnt].nxt=head[u],e[cnt].lim=w; e[cnt].to=v;

		return head[u]=cnt,void();

	}

	queue<int>q;

	inline bool bfs()

	{

		memset(dep,-1,sizeof(dep)); dep[s]=0;

		while(q.size()) q.pop(); q.push(s);

		while(!q.empty())

		{

			int fr=q.front(); q.pop();

			for(int i=head[fr];i;i=e[i].nxt)

			{

				int tr=e[i].to;

				if(dep[tr]==-1&&e[i].lim) dep[tr]=dep[fr]+1,q.push(tr);

			}

		}

		return dep[t]!=-1;

	 }

	inline int dfs(int now,int in)

	{

		if(now==t) return in; int out=0;

		for(int i=head[now];i&&in;i=e[i].nxt)

		{

			int tr=e[i].to;

			if(e[i].lim&&dep[tr]==dep[now]+1)

			{

				int res=dfs(tr,min(in,e[i].lim));

				in-=res; out+=res; e[i].lim-=res;

				e[i^1].lim+=res;

			}

		} if(!out) dep[now]=-1; return out;

	}

	signed main()

	{

		n=read(),m=read(); s=1,t=n;

		for(int i=1,u,v,w;i<=m;++i)

		{

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

			add(u,v,w*a+1);  add(v,u,0);

		}

		while(bfs()) ans+=dfs(s,1e17);

		printf("%lld %lld\n",ans/a,ans%a);

		return 0;

	}

}

signed main(){return yspm::main();}

没怎么压行，应该挺可读的

巴特西

LGOJ1344 追查坏牛奶

Description

Solution

Code

最新文章

热门文章