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++)
    {
        dep[i]=0x3f3f3f3f;
        ans[i]=0;
        vir[i]=head[i];
    }
    queue<int>q;
    q.push(0);
    dep[0]=0;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        ans[now]=0;
        for(int i=head[now];~i;i=node[i].next)
        {
            int to=node[i].vi;
            if(dep[to]>dep[now]+1&&node[i].ti)
            {
                dep[to]=dep[now]+1;
                if(ans[to]==0)
                {
                    ans[to]=1;
                    q.push(to);
                }
            }
        }
    }
    if(dep[2*n+1]!=0x3f3f3f3f) return 1;
    return 0;
}
int dfs(int u,int flow)
{
    int rlow=0;
    if(u==2*n+1)//如果到達了終點
    {
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int i=vir[u];~i;i=node[i].next)
    {
        vir[u]=i;
        int d=node[i].vi;
        if(node[i].ti&&dep[d]==dep[u]+1)
        {
            if(rlow=dfs(d,min(flow-used,node[i].ti)))
            {
                used+=rlow;
                node[i].ti-=rlow;
                node[i^1].ti+=rlow;
                if(used==flow) break;
            }
        }
    }
    return used;
}
int Dinic()
{
    while(bfs())
    {
        dfs(0,inf);
    }
    return maxflow;
}
int check(int f)
{
    memset(head,-1,sizeof(head));
    cent=0;
    for(int i=1;i<=n;i++)
    {
        add(0,i,1);//將0作為超級源點,2*n+1作為超級匯點
        add(i,0,0);
        add(n+i,2*n+1,1);
        add(2*n+1,n+i,0);
    }
    for(int i=1;i<=m;i++)
    {
        if(rode[i].t<=f)
        {//如果這條邊滿足要求
            add(rode[i].u,rode[i].v+n,1);
            add(rode[i].v+n,rode[i].u,0);
        }
    }
    maxflow=0;
    Dinic();
    if(maxflow<n) return 0;
    else return 1; 
}
int main()
{
    scanf("%d%d",&n,&m);
    int minn=inf,maxn=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&rode[i].u,&rode[i].v,&rode[i].t);
        if(rode[i].t<minn) minn=rode[i].t;
        if(rode[i].t>maxn) maxn=rode[i].t;
    }
    int l=minn,r=maxn;
    int res=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(check(mid))
        {
            res=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    printf("%d\n",res);
    //system("pause");
    return 0;
}