Codeforces —1423B. Valuable Paper（二分+网络流求最大匹配）

Codeforces —1423B. Valuable Paper（二分+网络流求最大匹配）

B. Valuable Paper

题目传送门：
B. Valuable Paper

题目大意：

给你n个飞机场和n个造纸厂，飞机厂和造纸厂需要一一对应。有m条道路连接飞机场和造纸厂，通过第i条道路的时间为ti。要使所需要的道路的最大时间最小。

思路：

二分道路的最大值，然后跑网络最大流求二分图最大匹配，看能否达到所有机场和造纸厂一一对应。

AC Code

//二分最大边，加上网络流跑二分图匹配
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,M=1e5+10,inf=1<<25;
struct Rode
{int u,v,t;
}rode[M];
int head[N*3],cent;
int n,m;//点数和边数
int maxflow;
int dep[N*3],ans[N*3],vir[N*3];
struct Node
{int ui,vi;int ti;int next;
}node[M*4];
void add(int u,int v,int t)
{node[cent].vi=v;node[cent].ti=t;node[cent].next=head[u];head[u]=cent++;
}
bool bfs()
{//分层for(int i=0;i<=2*n+1;i