BZOJ1570:[JSOI2008]Blue Mary的旅行 暴力+网络流

思路:

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

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

具体连边看代码.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
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]<T-S+1){
            if(u==T){
                for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])ins=i,Min=flow[stk[i]];
                for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min;
                u=end[stk[top=ins]^1];
            }
            if(u!=T&&!gap[d[u]-1])break;
            bool find=0;
            for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){
                find=1,ins=j;break;
            }
            if(find){stk[top++]=cur[u]=ins,u=end[ins];}
            else{
                Min=T-S+1;
                for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min)
                    cur[u]=j,Min=d[end[j]];
                if(!--gap[d[u]])break;
                ++gap[d[u]=Min+1];
                if(u!=S)u=end[stk[--top]^1];
            }
        }
        return re;
    }
}Stg;
 
struct Edge{
    int u,v,f;
}E[2510];
 
#define get(x,dep) ((dep-1)*n+x)
int main(){
    int n,m,T;scanf("%d%d%d",&n,&m,&T);
    register int i,j;
    for(i=1;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;
}