思路:

暴力枚举答案,然后将点分层,边总是从该层连向下一层.

然后判断最大流是不是满足题意.

具体连边看代码.

#include
#include
#include
#include
#include
using namespace std;
 
#define INF ~0U>>1
struct Solver{
    static const int V=50*100;
    static const int E=2450*100*2;
    int head[V],next[E],end[E],flow[E],ind;
    int d[V],gap[V],stk[V],top,cur[V];
    inline void reset(){
        ind=top=0,memset(head,-1,sizeof head);
    }
    inline void addedge(int a,int b,int f){
        int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;
    }
    inline void make(int a,int b,int f){
        /*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0);
    }
    inline void bfs(int T){
        static int q[V];int fr=0,ta=0;
        memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T;
        while(fr^ta){
            int i=q[fr++];
            for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1)
                ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j];
        }
    }
    inline int Maxflow(int S,int T){
        bfs(T),memcpy(cur,head,sizeof cur);
        int re=0,Min,ins,i,u=S;
        while(d[S]flow[stk[i]])ins=i,Min=flow[stk[i]];
                for(re+=Min,i=0;i<=m;++i)scanf("%d%d%d",&E;[i].u,&E;[i].v,&E;[i].f);
     
    int re;
    for(re=1;;++re){
        Stg.reset();
        for(i=1;i<=m;++i)for(j=1;j<=re;++j)Stg.make(get(E[i].u,j),get(E[i].v,j+1),E[i].f);
        for(j=1;j<=re;++j)Stg.make(0,get(1,j),INF);
        for(j=2;j<=re+1;++j)Stg.make(get(n,j),n*(re+1)+1,INF);
        int now=Stg.Maxflow(0,n*(re+1)+1);
        //printf("%d\n",now);
        if(now>=T)break;
    }
     
    printf("%d\n",re);
     
    return 0;
}