[BZOJ1733]神秘的挤奶机 二分+最大流

这题水得很哪.一看就是网络流模型,问经过的最大边权最小是多少.二分一下不就完了XwX

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 233
#define M 102333
using namespace std;
int n,m,t;
struct Node
{
	int x,y,z;
}e[M];
int head[N],to[M],next[M],f[M],tot=1;
inline void add(int x,int y,int z)
{
	to[++tot]=y;f[tot]=1;next[tot]=head[x];head[x]=tot;
	to[++tot]=x;f[tot]=1;next[tot]=head[y];head[y]=tot;
}
void clean()
{
	memset(head,0,sizeof head);
	memset(to,0,sizeof to);
	memset(next,0,sizeof next);
	memset(f,0,sizeof f);
	tot=1;
}
queue<int>q;
int dis[N];
bool bfs()
{
	memset(dis,-1,sizeof dis);
	while(!q.empty())q.pop();
	q.push(1);dis[1]=1;
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i;i=next[i])if(f[i]>0&&dis[to[i]]<0)
		{
			dis[to[i]]=dis[x]+1;
			if(to[i]==n)return 1;
			q.push(to[i]);
		}
	}
	return 0;
}
int dinic(int x,int flow)
{
	if(x==n)return flow;
	int a,temp=flow;
	for(int i=head[x];i;i=next[i])if(f[i]&&dis[to[i]]==dis[x]+1)	
	{
		a=dinic(to[i],min(f[i],temp));
		if(!a)dis[to[i]]=-1;
		else
		{
			f[i]-=a;f[i^1]+=a;
			temp-=a;
			if(!temp)break;
		}
	}
	return flow-temp;
}
int maxflow()
{
	int re=0;
	while(bfs())re+=dinic(1,1<<30);
	return re;
}
int main()
{
	cin>>n>>m>>t;
	for(int x,y,z,i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		e[i].x=x,e[i].y=y,e[i].z=z;
	}
	int l=0,r=1002333;
	while(l<r)
	{
		clean();
		int mid=(l+r)>>1;
		for(int i=1;i<=m;i++)if(e[i].z<=mid)add(e[i].x,e[i].y,e[i].z);
		if(maxflow()>=t)r=mid;
		else l=mid+1;
	}
	printf("%d",l);
	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注