题 目 链 接

二分图匹配，同时记录一下边权，试一下，感觉会t
好吧，直接wa了...

这题感觉好难...思维上感觉很有跳跃性...怎么才1900；
二分图最大匹配 套了个 二分我就不会了呜呜呜，我太菜了...

分析一下：

1. 我们考虑直接二分答案，显然具有二分性（想过二分，但是没细想就pass了...）

2. 对于二分的一个值mid，下面考虑如何check？？？
题目给了一个重要的提示（没看到呜呜呜），就是无法匹配的输出-1，
这就提示了我们作为check的判断条件；

也就是对于mid，我们只用<=mid的边(重新建图)，判断是否所有机场和工厂都匹配(最大匹配)；
如果可以，则mid缩小，否则扩大；

求最大匹配的话有两种方法：
(1) 匈牙利算法
(2) 网络流

艹了，匈牙利算法Tle了...只能写网络流就离谱...
(麻了，现在1900都要用网络流了嘛...)

(2)网络流的话就要转换一下了！
建图就搞个 源点 和 汇点
即最大匹配 <=> 容量都是1的最大流

下面配上两份代码（dinic，匈牙利算法）

dinic

const int N = 17, maxn = 3e4+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int h[maxn],ne[400010],e[400010],f[400010],idx;

int d[maxn];
int cur[maxn];  //当前弧优化

struct node
{
    int a,b;
    int c;
}no[100010];

int n,m;
int S,T;

void add(int a,int b,int c)
{
    e[idx]=b; f[idx]=c; ne[idx]=h[a]; h[a]=idx++;
    e[idx]=a; f[idx]=0; ne[idx]=h[b]; h[b]=idx++;   
}

// //下面是dinic算法
bool bfs()
{
    queue<int> q;
    memset(d,-1,sizeof d);

    q.push(S);
    d[S] = 0;
    cur[S] = h[S];

    while(q.size())
    {
        int t = q.front();
        q.pop();

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j = e[i];

            if(d[j] == -1 && f[i])
            {
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;
                q.push(j);
            }
        }
    }
    return false;
}

int find(int u,int limit)
{
    if(u == T) return limit;
    int flow = 0;

    for(int i=cur[u];i!=-1 && flow < limit;i=ne[i])
    {
        cur[u] = i;
        int j = e[i];

        if(d[j] == d[u] + 1 && f[i])
        {
            int t = find(j,min(f[i],limit-flow));

            if(!t) d[j] = -1;

            f[i] -= t; f[i^1] +=t;
            flow += t;
        }
    }
    return flow;    
}

int dinic()
{
    int r = 0,flow;
    while(bfs())
    {
        while(flow = find(S,inf)) r += flow;
    }
    return r;
}


bool check(int mid)
{
    //重新建图
    idx = 0;
    memset(h,-1,sizeof h);

    //0作为源点，2*n+1作为汇点
    S = 0, T = 2*n+1;
    for(int i=1;i<=n;i++)
    {
        add(0,i,1);
        add(i+n,2*n+1,1);
    }

    for(int i=1;i<=m;i++)
        if(no[i].c <= mid)
        {
            int a = no[i].a;
            int b = no[i].b;
            int c = no[i].c;

            add(a,b+n,c);   //注意要+偏移量
        }

    int ans = dinic();  //跑一下最大流

    if(ans < n) return false;
    return true;
}

int main()
{
    scanf("%d %d",&n,&m);

    int maxi = 0;
    int mini = inf;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);

        maxi = max(maxi,c);
        mini = min(mini,c);

        no[i] = {a,b,c};
    }

    int l = mini;
    int r = maxi;

    int ans = -1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid, ans = mid;
        else l = mid + 1;
    }

    printf("%d\n",ans);

    return 0;
}

-------------------分界线-----------------
下面是匈牙利（t了）

const int N = 17, maxn = 3e4+10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

int h[maxn],ne[200010],e[200010],w[200010],idx;

struct node
{
    int a,b;
    int c;
}no[200010];

int n,m;

int vis[maxn];
int match[maxn];

inline void add(int a,int b,int c)
{
    e[idx]=b; ne[idx]=h[a]; w[idx]=c; h[a]=idx++;
}

inline bool find(int x)
{
    for(int i=h[x];i!=-1;i=ne[i])
    {
        int j = e[i];

        if(!vis[j])
        {
            vis[j] = 1;

            if(match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}

inline bool check(int mid)
{
    //重新建图
    idx = 0;
    memset(h,-1,sizeof h);

    for(int i=1;i<=m;i++)
    {
        if(no[i].c > mid) break;

        int a = no[i].a;
        int b = no[i].b;
        int c = no[i].c;

        add(a,b+n,c);   //注意要+偏移量
        add(b+n,a,c);

    }

    //下面二分图匹配
    memset(match,0,sizeof match);   
    int cnt = 0;    //最大匹配数
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof vis);
        if(find(i)) cnt++;
    }

    if(cnt < n) return false;
    return true;
}

bool cmp(node no1,node no2)
{
    return no1.c < no2.c;
}

int main()
{
    scanf("%d %d",&n,&m);

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);

        no[i] = {a,b,c};
    }

    sort(no+1,no+1+m,cmp);

    int l = no[1].c;
    int r = no[m].c;

    int ans = -1;
    while(l < r)
    {
        int mid = l + r >> 1;
        if(check(mid)) r = mid, ans = mid;
        else l = mid + 1;
    }

    printf("%d\n",ans);

    return 0;
}