bzoj3572又TM是网络流

= =我承认我写网络流写疯了

= =我承认前面几篇博文都是扯淡，我写的是垃圾dinic（根本不叫dinic）

= =我承认这道题我调了半天

= =我承认我这道题一开始是T的，后来换上真正的dinic才过

= =我承认我还没理解dinic

= =我承认我一直到处改最后才发现输入顺序错了

= =我承认我已经疯了

= =我承认我写我承认上瘾了

回正题：这道题建图比较基础（但终于不是板题了），对于每个任务和每一天都建一个点（感觉把任务拆成若干点还能写二分图匹配），然后限制流量，然后判断是否满了

 #include <cstdio>

 #define INF 2147483647

 int n,m,N,need,p,q,o,zl,h,t,T,tt,ans,fir[],nex[],to[],flo[],d[],l[];

 inline int min(int p,int q){    return(p<q)?p:q;}

 inline void add(int p,int q,int o){    to[++N]=q;flo[N]=o;nex[N]=fir[p];fir[p]=N;

                                     to[++N]=p;flo[N]=;nex[N]=fir[q];fir[q]=N;}

 int dfs(int now,int flow,int sum)

 {

     if(now==n+) return flow;

     for(int i=fir[now];i && (flow>sum);i=nex[i])

         if(d[to[i]]==d[now]+ && flo[i])

             zl=dfs(to[i],min(flow,flo[i]),),sum+=zl,flo[i]-=zl,flo[i^]+=zl;

     if(sum==) d[now]=;

     return sum;

 }

 bool bfs()

 {

     for(int i=;i<=n+;i++) d[i]=;

     for(h=,t=,l[]=,d[]=;h<=t;h++)

         for(int i=fir[l[h]];i;i=nex[i])

             if(!d[to[i]] && flo[i])

                 l[++t]=to[i],d[l[t]]=d[l[h]]+;

     return d[n+];

 }

 int main()

 {

     for(scanf("%d",&T),tt=;tt<=T;tt++)

     {

         scanf("%d%d",&n,&m);need=;N=;

         for(int i=;i<=n+;i++) fir[i]=;

         for(int i=;i<=n;i++)

         {

             scanf("%d%d%d",&o,&p,&q),add(,i,o),need+=o;

             for(int j=p;j<=q;j++) add(i,j+n,);

         }

         for(int i=;i<=;i++)

             add(i+n,n+,m);

         for(ans=;bfs();ans+=dfs(,INF,));

         printf((ans==need)?"Case %d: Yes\n\n":"Case %d: No\n\n",tt);

     }

     return ;

 }

巴特西

bzoj3572又TM是网络流

最新文章

热门文章