【Luogu1344】追查坏牛奶（最小割）

题面

洛谷

题解

裸的最小割，但是要求边的数量最小。

怎么办呢？给每条边的权值额外加上一个很大的值就了。

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

#define ll long long

#define pls 2000000001

#define MAX 50

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;ll w;}e[3000];

int h[MAX],cnt=2;

inline void Add(int u,int v,ll w)

{

	e[cnt]=(Line){v,h[u],w};h[u]=cnt++;

	e[cnt]=(Line){u,h[v],0};h[v]=cnt++;

}

int n,m,S,T;

int level[MAX];

bool bfs()

{

	for(int i=S;i<=T;++i)level[i]=0;

	queue<int> Q;Q.push(S);level[S]=1;

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=h[u];i;i=e[i].next)

			if(!level[e[i].v]&&e[i].w)

				level[e[i].v]=level[u]+1,Q.push(e[i].v);

	}

	return level[T];

}

ll dfs(int u,ll flow)

{

	if(u==T||!flow)return flow;

	ll ret=0;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;ll d;

		if(e[i].w&&level[v]==level[u]+1)

		{

			d=dfs(v,min(flow,e[i].w));

			ret+=d;flow-=d;

			e[i].w-=d;e[i^1].w+=d;

		}

	}

	return ret;

}

ll Dinic()

{

	ll ret=0;

	while(bfs())ret+=dfs(S,1e18);

	return ret;

}

int main()

{

	n=read();m=read();S=1;T=n;

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

	{

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

		Add(u,v,w+pls);

	}

	ll ans=Dinic();

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

	return 0;

}