poj：2455 Secret Milking Machine 秘密挤奶机（二分+最大流）

矫情吗；* 2022-12-27 07:57 152阅读 0赞

原题链接：[poj2455：Secret Milking Machine][poj2455_Secret Milking Machine]

### 题目大意 ###

题目说现在有n个点，p条边，每条边只能走一次，现在要从1号点到n号点走t次，求出所有走的边的最大值，使这个最大值最小。

### 思路 ###

这是一道**最小化最大值**的题，一般一看到最大化最小值或最小化最大值这类的题，首先就要想到是[二分（详细可以看这）][Link 1]，然后我们就要判断答案是否有二段性或单调性来判断能否二分。

首先我们设答案在\[l , r\]区间内，假设一个值x，我们只用长度小于x的边，也可以从1到n走t次，然后答案肯定在\[l , x\]区间内，我们可以找一个更小的临界值；若我们只用长度小于x的边，从1到n走不了t次，说明我们要用到路的长度应该更大一点，则答案一定在\[x+1 , r\]区间内。

通过这个思路我们就可以看出答案具有二段性（单调性），所以我们就用**二分找这个临界值**，这就是最小化的最大值了。那么现在的问题就是如何判断我们能不能只用长度小于这个x的边，能走t次，就是如何写我们的judge函数，我们可以使用[最大流][Link 2]来判断。

我们可以按照这个图建一个网络流，给每条长度小于x的边流量给1，说明只能走一次；大于x的边流量给0，说明不能走。源点设为1，汇点设为n，求一遍源点到汇点的最大流，就能得到我们能走多少遍，判断是否大于等于要求的t即可。

那么还有最后一个问题，就是无向图向有向图的转换。题目给定的是无向图，而网络流用的是有向图，那么我们在建图时，对于一条无向边（u，v），我们建两条有向边u -> v和v -> u两条有向边，而且我们可以证出这个依然满足网络流的理论，是一个完整的流网络，所以我们就可以直接借助最大流来判断。

### 代码模板 ###

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    const int N = 210,M = 80010,INF = 0x3f3f3f3f;
    
    int n,m,s,t,k,dis[N],cur[N];
    int e[M],w[M],f[M],ne[M],h[N],idx;
    
    void add(int a,int b,int c)	//加边函数
    { 
    	e[idx] = b;
    	w[idx] = c;
    	ne[idx] = h[a];
    	h[a] = idx++;
    }
    
    bool bfs()		//dinic板子
    { 
    	queue<int> q;
    	memset(dis,-1,sizeof dis);
    	q.push(s);
    	dis[s] = 0;
    	cur[s] = h[s];
    	while(q.size())
    	{ 
    		int u = q.front();
    		q.pop();
    		for(int i = h[u];~i;i = ne[i])
    		{ 
    			int v = e[i];
    			if(dis[v] == -1 && f[i])
    			{ 
    				dis[v] = dis[u] + 1;
    				cur[v] = h[v];
    				if(v == t)
    					return 1;
    				q.push(v);
    			}
    		}
    	}
    	return 0;
    }
    
    int dfs(int u,int limit)
    { 
    	if(u == t)
    		return limit;
    	int flow = 0;
    	for(int i = cur[u];~i;i = ne[i])
    	{ 
    		cur[u] = i;
    		int v = e[i];
    		if(dis[v] == dis[u]+1 && f[i])
    		{ 
    			int minf = dfs(v,min(f[i],limit-flow));
    			f[i] -= minf;
    			f[i^1] += minf;
    			flow += minf;
    			if(flow == limit)
    				return flow;
    		}
    	}
    	return flow;
    }
    
    int dinic()
    { 
    	int ans = 0;
    	while(bfs())
    		ans += dfs(s,INF);
    	return ans;
    }
    
    bool judge(int m)	//judge函数
    { 
    	for(int i = 0;i < idx;i++)	//循环所有边
    	{ 
    		if(w[i] > m)		//边长大于m的流量设为0
    			f[i] = 0;
    		else			//小于m的流量设为1
    			f[i] = 1;
    	}
    	return dinic() >= k;		//做dinic，判断是否大于等于k
    }
    
    int main()
    { 
    	cin >> n >> m >> k;
    	s = 1,t = n;
    	memset(h,-1,sizeof h);
    	while(m--)
    	{ 
    		int a,b,c;
    		cin >> a >> b >> c;
    		add(a,b,c);	//存图，无向图建两条边，a到b和b到a
    		add(b,a,c);
    	}
    
    	int l = 1,r = 1e6;	//答案的范围就是题目给定的1-1e6
    	while(l < r)
    	{ 
    		int mid = l+r >> 1;	//二分，mid是中点
    		if(judge(mid))
    			r = mid;
    		else
    			l = mid + 1;
    	}
    	cout << r << endl;	//最后l和r一样，输出哪个都可以
    
    	return 0;
    }

[poj2455_Secret Milking Machine]: http://poj.org/problem?id=2455
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/109027273
[Link 2]: https://blog.csdn.net/qq_45735851/article/details/109717899